In-route nearest neighbor queries

Jin Soung Yoo, Shashi Shekhar

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


Nearest neighbor query is one of the most important operations in spatial databases and their application domains, such as location-based services and advanced traveler information systems. 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. Extensive experiments using real road map datasets are conducted to examine the behaviors of the solutions in terms of five parameters affecting the performance. The overall experiments show that our strategy to reduce the expensive path computations to minimize the response time is reasonable. The spatial distance join-based method always shows better performance with fewer path computations compared to the recursive methods. 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 decrease with increases 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)
Pages (from-to)117-137
Number of pages21
Issue number2
StatePublished - Jun 2005


  • Location-based services
  • Nearest neighborhood query
  • Road network
  • Route


Dive into the research topics of 'In-route nearest neighbor queries'. Together they form a unique fingerprint.

Cite this