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

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.