Top-$k$ Community Similarity Search Over Large-Scale Road Networks
Niranjan Rai, Xiang Lian
Abstract
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, namely <i>top-<inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="lian-ieq3-3243177.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula> community similarity search</i> ( <inline-formula><tex-math notation="LaTeX">$Top\text{-}kCS^{2}$</tex-math></inline-formula> ) over road networks, which efficiently and effectively obtains <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> spatial communities that are the most similar to a given query community in road-network graphs. In order to efficiently and effectively tackle the <inline-formula><tex-math notation="LaTeX">$Top\text{-}kCS^{2}$</tex-math></inline-formula> problem, in this paper, we will design an effective similarity measure between spatial communities, and propose a framework for retrieving <inline-formula><tex-math notation="LaTeX">$Top\text{-}kCS^{2}$</tex-math></inline-formula> query answers, which integrates offline pre-processing and online computation phases. Moreover, we also consider a variant, namely <i>continuous top-<inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="lian-ieq8-3243177.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula> community similarity search</i> ( <inline-formula><tex-math notation="LaTeX">$CTop\text{-}kCS^{2}$</tex-math></inline-formula> ), 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 <inline-formula><tex-math notation="LaTeX">$CTop\text{-}kCS^{2}$</tex-math></inline-formula> query answers. Extensive experiments have been conducted on real and synthetic data sets to confirm the efficiency and effectiveness of our proposed <inline-formula><tex-math notation="LaTeX">$Top\text{-}kCS^{2}$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$CTop\text{-}kCS^{2}$</tex-math></inline-formula> approaches under various parameter settings.