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 ScholarDigital 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
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 ...
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