Nearest Close Friend Query in Road-Social Networks


Zijun Chen, Ruoyu Jiang, Wenyuan Liu




Nearest close friend query (kℓNCF) in geo-social networks, aims to find the k nearest user objects from among the ℓ-hop friends of the query user. Existing efforts on kℓ-NCF find the user objects in the Euclidean space. In this paper, we study the problem of nearest close friend query in road-social networks. We propose two methods. One is based on Dijkstra algorithm, and the other is based on IS-Label. For the Dijkstra-based method, Dijkstra algorithm is used to traverse the user objects needed. For the label-based method, we make use of IS-Label to calculate the distance between two vertices to avoid traversing the edges that do not contain the desired user object. For each method, we propose effective termination condition to terminate the query process early. Finally, we conduct a variety of experiments on real and synthetic datasets to verify the efficiency of the proposed methods.