Fast nearest neighbor search on road networks

Haibo HU*, Dik Lun Lee, Jianliang XU

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

58 Citations (Scopus)


Nearest neighbor (NN) queries have been extended from Euclidean spaces to road networks. Existing approaches are either based on Dijkstra-like network expansion or NN/distance precomputation. The former may cause an explosive number of node accesses for sparse datasets because all nodes closer than the NN to the query must be visited. The latter, e.g., the Voronoi Network Nearest Neighbor (V N3) approach, can handle sparse datasets but is inappropriate for medium and dense datasets due to its high precomputation and storage overhead. In this paper, we propose a new approach that indexes the network topology based on a novel network reduction technique. It simplifies the network by replacing the graph topology with a set of interconnected tree-based structures called SPIE's. An nd index is developed for each SPIE and our new (k)NN search algorithms on an SPIE follow a predetermined tree path to avoid costly network expansion. By mathematical analysis and experimental results, our new approach is shown to be efficient and robust for various network topologies and data distributions.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings
PublisherSpringer Verlag
Number of pages18
ISBN (Print)3540329609, 9783540329602
Publication statusPublished - 2006
Event10th International Conference on Extending Database Technology, EDBT 2006 - Munich, Germany
Duration: 26 Mar 200631 Mar 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3896 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th International Conference on Extending Database Technology, EDBT 2006

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Fast nearest neighbor search on road networks'. Together they form a unique fingerprint.

Cite this