Processing in-route nearest neighbor queries: A comparison of alternative approaches

Shashi Shekhar, Jin Soung Yoo

Research output: Contribution to conferencePaper

49 Scopus citations

Abstract

Nearest neighbor query is one of the most important operations in spatial databases and their application domains, e.g., location-based services, advanced traveler information systems, etc. This paper addresses the problem of finding the in-route nearest neighbor (IRNN) for a query object tuple which consists of a given route with a destination and a current location on it. The IRNN is a facility instance via which the detour from the original route on the way to the destination is smallest. This paper addresses four alternative solution methods. Comparisons among them are presented using an experimental framework. Several experiments using real road map datasets are conducted to examine the behavior of the solutions in terms of three parameters affecting the performance. Our experiments show that the computation costs for all methods except the precomputed zone-based method increase with increases in the road map size and the query route length but decreases with increase in the facility density. The precomputed zone-based method shows the most efficiency when there are no updates on the road map.

Original languageEnglish (US)
Pages9-16
Number of pages8
StatePublished - Dec 1 2003
EventGIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems - New Orleans, LA, United States
Duration: Nov 7 2003Nov 8 2003

Other

OtherGIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems
CountryUnited States
CityNew Orleans, LA
Period11/7/0311/8/03

Keywords

  • Advanced traveler information systems
  • Location-based services
  • Nearest neighborhood query
  • Road network
  • Route

Fingerprint Dive into the research topics of 'Processing in-route nearest neighbor queries: A comparison of alternative approaches'. Together they form a unique fingerprint.

  • Cite this

    Shekhar, S., & Yoo, J. S. (2003). Processing in-route nearest neighbor queries: A comparison of alternative approaches. 9-16. Paper presented at GIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems, New Orleans, LA, United States.