Distance indexing on road networks

Haibo Hu, Dik Lun Lee, Victor C.S. Lee

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

78 Citations (Scopus)

Abstract

2006 VLDB Endowment, ACM. The processing of kNN and continuous kNN queries on spatial network databases (SNDB) has been intensively studied recently. However, there is a lack of systematic study on the computation of network distances, which is the most fundamental difference between a road network and a Euclidean space. Since the online Dijkstra's algorithm has been shown to be efficient only for short distances, we propose an efficient index, called distance signature, for distance computation and query processing over long distances. Distance signature discretizes the distances between objects and network nodes into categories and then encodes these categories. To minimize the storage and search costs, we present the optimal category partition, and the encoding and compression algorithms for the signatures, based on a simplified network topology. By mathematical analysis and experimental study, we showed that the signature index is efficient and robust for various data distributions, query workloads, parameter settings and network updates.
Original languageEnglish
Title of host publicationVLDB 2006 - Proceedings of the 32nd International Conference on Very Large Data Bases
PublisherAssociation for Computing Machinery
Pages894-905
Number of pages12
Volume2006-January
ISBN (Print)1595933859, 9781595933850
Publication statusPublished - 1 Jan 2006
Externally publishedYes
Event32nd International Conference on Very Large Data Bases, VLDB 2006 - Seoul, Korea, Republic of
Duration: 12 Sep 200615 Sep 2006

Conference

Conference32nd International Conference on Very Large Data Bases, VLDB 2006
Country/TerritoryKorea, Republic of
CitySeoul
Period12/09/0615/09/06

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems
  • Software
  • Information Systems and Management

Cite this