Approximate indexing in road network databases

Sang Chul Lee, Sang Wook Kim, Junghoon Lee, Jae Soo Yoo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

In this paper, we address approximate indexing for efficient processing of k-nearest neighbor(k-NN) queries in road network databases. Previous methods suffer from either serious performance degradation in query processing or large storage overhead because they did not employ indexing mechanisms based on their network distances. To overcome these drawbacks, we propose a novel method that builds an index on those objects in a road network by approximating their network distances and processes k-NN queries efficiently by using that index. Also, we verify the superiority of the proposed method via extensive experiments using the real-life road network databases.

Original languageEnglish
Title of host publication24th Annual ACM Symposium on Applied Computing, SAC 2009
Pages1568-1572
Number of pages5
DOIs
StatePublished - 2009 Dec 1
Event24th Annual ACM Symposium on Applied Computing, SAC 2009 - Honolulu, HI, United States
Duration: 2009 Mar 82009 Mar 12

Publication series

NameProceedings of the ACM Symposium on Applied Computing

Other

Other24th Annual ACM Symposium on Applied Computing, SAC 2009
CountryUnited States
CityHonolulu, HI
Period09/03/809/03/12

Keywords

  • Approximate indexing
  • Data structures
  • K-nearest neighbor queries
  • Road network databases

Fingerprint Dive into the research topics of 'Approximate indexing in road network databases'. Together they form a unique fingerprint.

  • Cite this

    Lee, S. C., Kim, S. W., Lee, J., & Yoo, J. S. (2009). Approximate indexing in road network databases. In 24th Annual ACM Symposium on Applied Computing, SAC 2009 (pp. 1568-1572). (Proceedings of the ACM Symposium on Applied Computing). https://doi.org/10.1145/1529282.1529632