Progressive Top-K Nearest Neighbors Search in Large Road Networks

Publication Type:
Conference Proceeding
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2020, pp. 1781-1795
Issue Date:
Filename Description Size
main.pdfAccepted version1.43 MB
Adobe PDF
Full metadata record
© 2020 Association for Computing Machinery. Computing top-k nearest neighbors (kNN) is a fundamental problem in road networks. Existing solutions either need a complicated parameter configuration in index construction or incur high costs when scanning an unbounded number of vertices in query processing. In this paper, we propose a novel parameter-free index-based solution for the kNN query based on the concept of tree decomposition in large road networks. Based on our index structure, we propose an efficient and progressive algorithm that returns each result in a bounded delay. We also optimize the index structure, which improves the efficiency of both index construction and index maintenance in large road networks. We conduct extensive experiments to show the efficiency of our proposed algorithms and the effectiveness of our optimization techniques in real-world road networks from ten regions.
Please use this identifier to cite or link to this item: