Fast nearest neighbor search on road networks

Haibo Hu, Dik Lun Lee, Jianliang Xu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

45 Citations (Scopus)

Abstract

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 N 3) 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
Pages186-203
Number of pages18
Publication statusPublished - 10 Jul 2006
Externally publishedYes
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

Conference

Conference10th International Conference on Extending Database Technology, EDBT 2006
CountryGermany
CityMunich
Period26/03/0631/03/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this