Finding all nearest neighbors with a single graph traversal

• Main Authors: XU, Yixin, QI Jianzhong, BOROVICA‐GAJIC Renata, KULIK Lars
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: All nearest neighbors; Euclidean spaces; Index based algorithm; Nearest neighbor algorithm; Nearest neighbor queries; Nearest neighbors; State of the art; Urban environments; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/8276; https://ink.library.smu.edu.sg/context/sis_research/article/9279/viewcontent/Finding_All_Nearest_Neighbors_with_a_Single_Graph_Traversal.pdf
• Institution: Singapore Management University

Finding the nearest neighbor is a key operation in data analysis and mining. An important variant of nearest neighbor query is the all nearest neighbor (ANN) query, which reports all nearest neighbors for a given set of query objects. Existing studies on ANN queries have focused on Euclidean space. Given the widespread occurrence of spatial networks in urban environments, we study the ANN query in spatial network settings. An example of an ANN query on spatial networks is finding the nearest car parks for all cars currently on the road. We propose VIVET, an index-based algorithm to efficiently process ANN queries. VIVET performs a single traversal on a spatial network to precompute the nearest data object for every vertex in the network, which enables us to answer an ANN query through a simple lookup on the precomputed nearest neighbors. We analyze the cost of the proposed algorithm both theoretically and empirically. Our results show that the algorithm is highly efficient and scalable. It outperforms adapted state-of-the-art nearest neighbor algorithms in both precomputation and query processing costs by more than one order of magnitude.