Nearest Close Friend Query in Road-Social Networks

Zijun Chen^{1, 2}, Ruoyu Jiang^{1, 2} and Wenyuan Liu^{1, 2}

School of Information Science and Engineering, Yanshan University
Qinhuangdao 066004, China
The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province
Qinhuangdao 066004, China
zjchen@ysu.edu.cn, jiangruoyu@stumail.ysu.edu.cn, wyliu@ysu.edu.cn

Abstract

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 conditon 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.

Key words

road-social networks, R-tree, IS-Label index, nearest neighbor query

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS210930031C

Publication information

Volume 19, Issue 3 (September 2022)
Year of Publication: 2022
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

Download Available in PDF
Portable Document Format

How to cite

Chen, Z., Jiang, R., Liu, W.: Nearest Close Friend Query in Road-Social Networks. Computer Science and Information Systems, Vol. 19, No. 3, 1283-1304. (2022), https://doi.org/10.2298/CSIS210930031C