Xiaobin Ma
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.
- S. Berchtold, C. Bohm, D. Keim, and H. Kriegel. A Cost Model for Nearest Neighbor in High-Dimensional Data Space. In PODS, pages 78--86, 1997.]] Google Scholar
Digital Library
- K. Cheung and A. Fu. Enhanced Nearest Neighbor Search on the R-tree. ACM SIGMOD Record, pages 16--21, 1998.]] Google ScholarDigital Library
- K. Clarkson. Fast Algorithms for the All-Nearest-Neighbors Problem. In FOCS, 1983.]]Google ScholarDigital Library
- J. G. Cleary. Analysis of an algorithm for finding nearest neighbor in Euclidean space. ACM Transactions on Mathematical Software, pages 183--192, June 1979.]] Google ScholarDigital Library
- A. Corral, Y. Manolopoulos, and M. Vassilakopoulos. Closest Pair Queries in Spatial Databases. In ACM SIGMOD, 2000.]] Google ScholarDigital Library
- A. Corral, Y. Manolopoulos, and M. Vassilakopoulos. Algorithms for Processing K-closest-pair Queries in Spatial Databases. Data and Knowledge Engineering, pages 67--104, 2004.]] Google ScholarDigital Library
- A. Corral, M. Vassilakopoulos, and Y. Manolopoulos. The impact of Buffering on Closest Pairs Queries Using R-Trees. In ADBIS'01, pages 41--54, 2001.]] Google ScholarDigital Library
- C. Yang and K.-I. Lin. A index structure for efficient reverse nearest neighbor queries. In ICDE, 2001.]] Google ScholarDigital Library
- J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logrithmic expected time. ACM Transactions on Mathematical Software, pages 209--226, September 1977.]] Google ScholarDigital Library
- H. Herhatosmanoglu, D. A. I. Stanoi, and A. Abbadi. Constrained Nearest Nieghbor Queries. In SSTD, 2001.]] Google ScholarDigital Library
- C. Hjaltason and H. Samet. Incremental Distance Join Algorithms for Spatial Databases. In ACM SIGMOD, 1998.]] Google ScholarDigital Library
- C. Hjaltason and H. Samet. Distance Browsing for Spatial Databases. ACM TODS, pages 265--318, 2 1999.]] Google ScholarDigital Library
- F. Korn and S. Muthukrishnan. Influence sets based on reverse nearest neighbor queries. In ACM SIGMOD, 2000.]] Google ScholarDigital Library
- F. Korn, S. Muthukrishnan, and D. Srivastava. Reverse nearest neighbor aggregates over data stream. In VLDB, 2002.]]Google ScholarCross Ref
- F. Li, D. Chen, M. Hadjieleftherious, G. Kollios, and S. Teng. On trip planning queries in spatial databases. In SSTD, 2005.]] Google ScholarDigital Library
- X. Ma, S. Shekhar, H. Xiong, and P. Zhang. Exploiting a page-level upper bound for multi-type nearest neighbor queries. In TR 05-008, CS, UMN, 2005.]]Google Scholar
- D. Papadias, Y. T. Q. Shen, and K. Mouratidis. Group nearest neighbor queries. In ICDE, 2004.]] Google ScholarDigital Library
- A. Papadopoulos and Y. Manolopoulos. Performance of Nearest Neighbor Queries in R-trees. In ICDT, pages 394--408, 1997.]] Google ScholarDigital Library
- F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer Verlag, 1985.]] Google ScholarDigital Library
- N. Roussopoulos and F. V. S. Kelly. Nearest Neighbor Queries. In SIGMOD, 1995.]] Google ScholarDigital Library
- M. Sharifzadeh, M. Kolahdouzan, and C. Shahabi. The optimal sequenced route query. In TR 05-840, CS, USC, January 2005.]]Google Scholar
- I. Stanoi, D. Agrawal, and A. E. Abbadi. Reverse nearest neighbor queries for dynamic databases. In SIGMOD workshop on Research Issues in data mining and knowledge discovery, 2000.]]Google Scholar
- I. Stanoi, M. Riedewald, D. Agrawal, and A. E. Abbadi. Discovery of influence sets in frequently updated databases. In VLDB, 2001.]] Google ScholarDigital Library
- Y. Tao, D. Papadias, and Q. Shen. Continuous Nearest Neighbor Search. In VLDB, 2002.]]Google ScholarDigital Library
- J. Zhang, N. Mamoulis, D. Papadias, and Y. Tao. All-Nearest-Neighbors Queries in Spatial Databases. In SSDBM, 2004.]]Google Scholar
Index Terms
- Exploiting a page-level upper bound for multi-type nearest neighbor queries
Recommendations
Multi-type nearest neighbor queries in road networks with time window constraints
GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsThis paper presents a study of Multi-type Nearest Neighbor (MTNN) Queries in road networks with time window constraints. Specifically, we provide a label correcting algorithm, which is based on a time aggregated multi-type graph. This algorithm gives ...
On multi-type reverse nearest neighbor search
This paper presents a study of the Multi-Type Reverse Nearest Neighbor (MTRNN) query problem. Traditionally, a reverse nearest neighbor (RNN) query finds all the objects that have the query point as their nearest neighbor. In contrast, an MTRNN query ...
Comments