다단계 친구 그리드를 이용한 효율적인 최근접 친구 질의 처리 기법

Abstract

스마트기기 및 소셜 네트워크의 확산으로 위치 기반 소셜 네트워크 서비스(Location-Based Social Network Services: LBSNS)가 지속적인 관심을 받고 있다. 예를 들어, 사용자는 공간 데이터를 이용해 행사 장소, 여행지, 거주지와 가까이 있는 사람을 검색할 수 있으며, 검색된 사람들과 사용자의 연결(친구) 관계 또한 소셜 데이터를 이용해 확인할 수 있다. 이에 따라, 공간 데이터와 소셜 네트워크 데이터를 모두 고려한 지오소셜 네트워크(Geo-Social Network)에 관한 연구가 활발히 진행되고 있다. 본 논문은 질의 점으로부터 가장 가까운 k명의 사용자 친구를 검색하는 k-Nearest Friends (kNF) 질의를 소개하고, 이를 효율적으로 처리하기 위한 색인구조인 다단계 친구 그리드(Multi-level Friends Grid: MFG)를 정의한다. 정의한 색인 구조를 활용하여 효율적인 k-Nearest Friends 질의 처리 기법을 제안하고 성능 평가를 통해 효율성을 입증한다.