Top-$k$ Community Similarity Search Over Large-Scale Road Networks

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 <italic>top-<inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="lian-ieq3-3243177.gif"/></alternatives></inline-formula> community similarity search</italic> (<inline-formula><tex-math notation="LaTeX">$Top\text{-}kCS^{2}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>T</mml:mi><mml:mi>o</mml:mi><mml:mi>p</mml:mi><mml:mtext>-</mml:mtext><mml:mi>k</mml:mi><mml:mi>C</mml:mi><mml:msup><mml:mi>S</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math><inline-graphic xlink:href="lian-ieq4-3243177.gif"/></alternatives></inline-formula>) over road networks, which efficiently and effectively obtains <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="lian-ieq5-3243177.gif"/></alternatives></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><alternatives><mml:math><mml:mrow><mml:mi>T</mml:mi><mml:mi>o</mml:mi><mml:mi>p</mml:mi><mml:mtext>-</mml:mtext><mml:mi>k</mml:mi><mml:mi>C</mml:mi><mml:msup><mml:mi>S</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math><inline-graphic xlink:href="lian-ieq6-3243177.gif"/></alternatives></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><alternatives><mml:math><mml:mrow><mml:mi>T</mml:mi><mml:mi>o</mml:mi><mml:mi>p</mml:mi><mml:mtext>-</mml:mtext><mml:mi>k</mml:mi><mml:mi>C</mml:mi><mml:msup><mml:mi>S</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math><inline-graphic xlink:href="lian-ieq7-3243177.gif"/></alternatives></inline-formula> query answers, which integrates offline pre-processing and online computation phases. Moreover, we also consider a variant, namely <italic>continuous top-<inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="lian-ieq8-3243177.gif"/></alternatives></inline-formula> community similarity search</italic> (<inline-formula><tex-math notation="LaTeX">$CTop\text{-}kCS^{2}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>C</mml:mi><mml:mi>T</mml:mi><mml:mi>o</mml:mi><mml:mi>p</mml:mi><mml:mtext>-</mml:mtext><mml:mi>k</mml:mi><mml:mi>C</mml:mi><mml:msup><mml:mi>S</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math><inline-graphic xlink:href="lian-ieq9-3243177.gif"/></alternatives></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><alternatives><mml:math><mml:mrow><mml:mi>C</mml:mi><mml:mi>T</mml:mi><mml:mi>o</mml:mi><mml:mi>p</mml:mi><mml:mtext>-</mml:mtext><mml:mi>k</mml:mi><mml:mi>C</mml:mi><mml:msup><mml:mi>S</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math><inline-graphic xlink:href="lian-ieq10-3243177.gif"/></alternatives></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><alternatives><mml:math><mml:mrow><mml:mi>T</mml:mi><mml:mi>o</mml:mi><mml:mi>p</mml:mi><mml:mtext>-</mml:mtext><mml:mi>k</mml:mi><mml:mi>C</mml:mi><mml:msup><mml:mi>S</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math><inline-graphic xlink:href="lian-ieq11-3243177.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$CTop\text{-}kCS^{2}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>C</mml:mi><mml:mi>T</mml:mi><mml:mi>o</mml:mi><mml:mi>p</mml:mi><mml:mtext>-</mml:mtext><mml:mi>k</mml:mi><mml:mi>C</mml:mi><mml:msup><mml:mi>S</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math><inline-graphic xlink:href="lian-ieq12-3243177.gif"/></alternatives></inline-formula> approaches under various parameter settings.