Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2018

Abstract

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.

Keywords

All nearest neighbors, Euclidean spaces, Index based algorithm, Nearest neighbor algorithm, Nearest neighbor queries, Nearest neighbors, State of the art, Urban environments

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

Proceedings of the 23rd International Conference on Database Systems for Advanced Applications, Gold Coast, Australia, May 21-24

First Page

221

Last Page

238

ISBN

9783319914510

Identifier

10.1007/978-3-319-91452-7_15

Publisher

Springer Nature

City or Country

Netherlands

Additional URL

https://doi.org/10.1007/978-3-319-91452-7_15

Download

Share

COinS