Exploiting a page-level upper bound for multi-type nearest neighbor queries

Xiaobin Ma, Shashi Shekhar, Hui Xiong, Pusheng Zhang

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

23 Scopus citations

Abstract

Given a query point and a collection of spatial features, a multi-type nearest neighbor (MTNN) query finds the shortest tour for the query point such that only one instance of each feature is visited during the tour. For example, a tourist may be interested in finding the shortest tour which starts at a hotel and passes through a post office, a gas station, and a grocery store. The MTNN query problem is different from the traditional nearest neighbor query problem in that there are many objects for each feature type and the shortest tour should pass through only one object from each feature type. In this paper, we propose an R-tree based algorithm that exploits a page-level upper bound for efficient computation in clustered data sets and finds optimal query results. We compare our method with a recently proposed method, RLORD, which was developed to solve the optimal sequenced route (OSR) query. In our view, OSR represents a spatially constrained version of MTNN. Experimental results are provided to show the strength of our algorithm and design decisions related to performance tuning.

Original languageEnglish (US)
Title of host publicationProceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems, ACM-GIS'06
Pages179-186
Number of pages8
DOIs
StatePublished - 2006
Event14th Annual ACM International Symposium on Advances in Geographic Information Systems, ACM-GIS'06 - Arlington, VA, United States
Duration: Nov 6 2006Nov 11 2006

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

Conference

Conference14th Annual ACM International Symposium on Advances in Geographic Information Systems, ACM-GIS'06
Country/TerritoryUnited States
CityArlington, VA
Period11/6/0611/11/06

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Keywords

  • GIS
  • Location-based service
  • MTNN query

Fingerprint

Dive into the research topics of 'Exploiting a page-level upper bound for multi-type nearest neighbor queries'. Together they form a unique fingerprint.

Cite this