Top-$k$ Community Similarity Search Over Large-Scale Road Networks
Niranjan Rai, Xiang Lian · IEEE Transactions on Knowledge and Data Engineering · 2023
With the urbanization and development of infrastructure, the community search over road networks has become increasingly important in many real applications such as urban/city planning, social study on local communities, and community recommendations by real estate agencies. In this article, we propose a novel problem, namelytop-$k$kcommunity similarity search($Top\text{-}kCS^{2}$) over road networks, which efficiently and effectively obtains$k$spatial communities that are the most similar to a given query community in road-network graphs. In order to efficiently and effectively tackle the$Top\text{-}kCS^{2}$problem, in this paper, we will design an effective similarity measure between spatial communities, and propose a framework for retrieving$Top\text{-}kCS^{2}$query answers, which integrates offline pre-processing and online computation phases. Moreover, we also consider a variant, namelycontinuous top-$k$kcommunity similarity search($CTop\text{-}kCS^{2}$), where the query community continuously moves along a query line segment. We develop an efficient algorithm to split query line segment into intervals, incrementally obtain similar candidate communities for each interval, and refine actual$CTop\text{-}kCS^{2}$query answers. Extensive experiments have been conducted on real and synthetic data sets to confirm the efficiency and effectiveness of our proposed$Top\text{-}kCS^{2}$and$CTop\text{-}kCS^{2}$approaches under various parameter settings.