Nick Roussopoulos
Abstract
A frequently encountered type of query in Geographic Information Systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires substantially different search algorithms than those for location or range queries. In this paper we present an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalize it to finding the k nearest neighbors. We also discuss metrics for an optimistic and a pessimistic search ordering strategy as well as for pruning. Finally, we present the results of several experiments obtained using the implementation of our algorithm and examine the behavior of the metrics and the scalability of the algorithm.
- Beck90 Beckmann, N., H.-P. Kriegel, R. Schneider and B. Seeger, "The R*-tree" an efficient and robust access method for points and rectangles," ACM SIGMOD, pp 322-331, May 1990. Google Scholar
Digital Library
- BKS93 Brinkhoff, T., Kriegel, H.P., and Seeger, B., "Efficient Processing of Spatial Joins Using R- trees," Proc. ACM SIGMOD, May 1993, pp. 237- 246. Google ScholarDigital Library
- FBF77 Friedman, J.H., Bentley, j.L., and Finkel, R.A., "An algorithm for finding the best matches in logarithmic expected time," ACM Trans. Math. Software, 3, September 1977, pp. 209-226. Google ScholarDigital Library
- Gutt84 Guttman, A., "R-trees,: A Dynamic index Structure for Spatial Searching," Proc. ACM SIG- MOD, pp. 47-57, June 1984. Google ScholarDigital Library
- HS78 Horowitz, E., Sahni, S., "Fundamentals of Computer Algorithms," Computer Science Press, 1978, pp. 370-421. Google ScholarDigital Library
- Jaga90 Jagadish, H.V., "Linear Clustering of Objects with Multiple Attributes," Proc. ACM SIGMOD, May 1990, pp. 332-342. Google ScholarDigital Library
- Kame94 Kamel, I. and Faloutsos, C., "Hilbert R- Tree: an Improved R-Tree Using Fractals," Proc. of VLDB, 1994, pp. 500-509. Google ScholarDigital Library
- Rous85 Roussopoulos, N. and D. Leifker, "Direct Spatial Search on Pictorial Databases Using Packed R-trees," Proc. ACM SIGMOD, May 1985. Google ScholarDigital Library
- Same89 Samet, H., "The Design & Analysis Of Spatial Data Structures," Addison-Wesley, 1989. Google ScholarDigital Library
- Same90 Samet, H., "Applications Of Spatial Data Structures, Computer Graphics, Image Processing and GIS," Addison-Wesley, 1990. Google ScholarDigital Library
- SRF87 Sellis T., Roussopoulos, N., and Faloutsos, C., "The R+-tree: A Dynamic Index for Multidimensional Objects," Proc. 13th international Conference on Very Large Data Bases, 1987, pp. 507-518. Google ScholarDigital Library
- Spro91 Sproull, R.F., "Refinements to Nearest- Neighbor Searching in k-Dimensional Trees," A1- gorithmica, 6, 1987, pp. 579-589.Google Scholar
Index Terms
- Nearest neighbor queries
Recommendations
Nearest neighbor queries
SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of dataA frequently encountered type of query in Geographic Information Systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires substantially different search algorithms than those for location or range ...
Approximate Direct and Reverse Nearest Neighbor Queries, and the k-nearest Neighbor Graph
SISAP '09: Proceedings of the 2009 Second International Workshop on Similarity Search and ApplicationsRetrieving the \emph{k-nearest neighbors} of a query object is a basic primitive in similarity searching. A related, far less explored primitive is to obtain the dataset elements which would have the query object within their own \emph{k}-nearest ...
K-Nearest Neighbor Finding Using MaxNearestDist
Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These ...
Comments