Nearest neighbor query processing using the network voronoi diagram

摘要

The purpose of this paper is twofold: to develop sound and complete rules, along with algorithms and data structures, to construct the network voronoi diagram (NVD) on a road network. To compute the NVD, attention is focused on how to distinguish divisible paths from others, i.e., those whose midpoints are exactly their border points. Research shows that the dominance relation introduced in this paper plays an important role in making that distinction. To generate and prune candidate paths concurrently, a border-point binary tree is introduced. The pre-computed NVD is organized as linked lists and is available for access by a NVD list-based query search method (NVDL), which can compute NN in a single step. Experiments show that the NVDL method reduces execution time by 28% for sparse data distribution on a real road network compared to the existing INE method. The NVDL's query time remains nearly constant regardless of how data points are distributed on the road network or where the query point is positioned. In addition, this approach prevents the NVDL from experiencing the slow convergence condition that often occurs when using the incremental approach.