Distance browsing in spatial databases

ABSTRACT

We compare two different techniques for browsing through a collection of spatial objects stored in an R-tree spatial data structure on the basis of their distances from an arbitrary spatial query object. The conventional approach is one that makes use of a k-nearest neighbor algorithm where k is known prior to the invocation of the algorithm. Thus if m < k neighbors are needed, the k-nearest neighbor algorithm has to be reinvoked for m neighbors, thereby possibly performing some redundant computations. The second approach is incremental in the sense that having obtained the k nearest neighbors, the k + 1st neighbor can be obtained without having to calculate the k + 1 nearest neighbors from scratch. The incremental approach is useful when processing complex queries where one of the conditions involves spatial proximity (e.g., the nearest city to Chicago with population greater than a million), in which case a query engine can make use of a pipelined strategy. We present a general incremental nearest neighbor algorithm that is applicable to a large class of hierarchical spatial data structures. This algorithm is adapted to the R-tree and its performance is compared to an existing k-nearest neighbor algorithm for R-trees [Rousseopoulos et al. 1995]. Experiments show that the incremental nearest neighbor algorithm significantly outperforms the k-nearest neighbor algorithm for distance browsing queries in a spatial database that uses the R-tree as a spatial index. Moreover, the incremental nearest neighbor algorithm usually outperforms the k-nearest neighber algorithm when applied to the k-nearest neighbor problem for the R-tree, although the improvement is not nearly as large as for distance browsing queries. In fact, we prove informally that at any step in its execution the incremental nearest neighbor algorithm is optimal with respect to the spatial data structure that is employed. Furthermore, based on some simplifying assumptions, we prove that in two dimensions the number of distance computations and leaf nodes accesses made by the algorithm for finding k neighbors is O(k + k).

REFERENCES

• 1: Paul M. Aoki, Generalizing "Search'' in Generalized Search Trees (Extended Abstract), Proceedings of the Fourteenth International Conference on Data Engineering, p.380-389, February 23-27, 1998
• 2: AREF, W. G. AND SAMET, H. 1992. Uniquely reporting spatial objects: Yet another operation for comparing spatial data structures. In Proceedings of the 5th Symposium on Spatial Data Handling (Charleston, SC, Aug.). 178-189.
• 3: AREF, W. G. AND SAMET, H. 1993. Estimating selectivity factors of spatial operations. In Optimization in Databases - Proceedings of the 5th International Workshop on Foundations of Models and Languages for Data and Objects (Aigen, Austria, Sept.). 31-40.
• 4: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 5: Ludger Becker , Ralf Hartmut Güting, Rule-based optimization and query processing in an extensible geometric database system, ACM Transactions on Database Systems (TODS), v.17 n.2, p.247-303, June 1992 [doi>10.1145/128903.128905]
• 6: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 7: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 8: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263671]
• 9: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 10: Marshall Bern, Approximate closest-point queries in high dimensions, Information Processing Letters, v.45 n.2, p.95-99, Feb. 26, 1993 [doi>10.1016/0020-0190(93)90222-U]
• 11: Sergey Brin, Near Neighbor Search in Large Metric Spaces, Proceedings of the 21th International Conference on Very Large Data Bases, p.574-584, September 11-15, 1995
• 12: A. J. Broder, Strategies for efficient incremental nearest neighbor search, Pattern Recognition, v.23 n.1-2, p.171-178, January 1990 [doi>10.1016/0031-3203(90)90057-R]
• 13: W. A. Burkhard , R. M. Keller, Some approaches to best-match file searching, Communications of the ACM, v.16 n.4, p.230-236, April 1973 [doi>10.1145/362003.362025]
• 14: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 15: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 16: EASTMAN, C. M. AND ZEMANKOVA, M. 1982. Partially specified nearest neighbor searches using k-d-trees. Inf. Process. Lett. 15, 2 (Sept.), 53-56.
• 17: Claudio Esperança , Hanan Samet, Orthogonal Polygons as Bounding Structures in Filter-Refine Query Processing Strategies, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.197-220, July 15-18, 1997
• 18: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 19: A. U. Frank , R. Barrera, The fieldtree: a data structure for geographic information systems, Proceedings of the first symposium on Design and implementation of large spatial databases, p.29-44, February 1990, Santa Barbara, California, United States
• 20: Michael L. Fredman , Robert Sedgewick , Daniel D. Sleator , Robert E. Tarjan, The pairing heap: a new form of self-adjusting heap, Algorithmica, v.1 n.1, p.111-129, Jan. 1986 [doi>10.1007/BF01840439]
• 21: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 22: FUKUNAGA, K. AND NARENDRA, P. M. 1975. A branch and bound algorithm for computing. IEEE Trans. Comput. 24, 7 (July), 750-753.
• 23: Oliver Günther , Hartmut Noltemeier, Spatial Database Indices for Large Extended Objects, Proceedings of the Seventh International Conference on Data Engineering, p.520-526, April 08-12, 1991
• 24: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 25: James Hafner , Harpreet S. Sawhney , Will Equitz , Myron Flickner , Wayne Niblack, Efficient Color Histogram Indexing for Quadratic Form Distance Functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.7, p.729-736, July 1995 [doi>10.1109/34.391417]
• 26: HENRICH, A. 1994. A distance-scan algorithm for spatial access structures. In Proceedings of the Second ACM Workshop on Geographic Information Systems (Gaithersburg, MD, Dec.). ACM Press, New York, NY, 136-143.
• 27: Andreas Henrich, The LSDh-Tree: An Access Structure for Feature Vectors, Proceedings of the Fourteenth International Conference on Data Engineering, p.362-369, February 23-27, 1998
• 28: A. Henrich , H. -W. Six , P. Widmayer, The LSD tree: spatial access to multidimensional and non-point objects, Proceedings of the 15th international conference on Very large data bases, p.45-53, July 1989, Amsterdam, The Netherlands
• 29: Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995
• 30: Erik G. Hoel , Hanan Samet, Efficient Processing of Spatial Queries in Line Segment Databases, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.237-256, August 28-30, 1991
• 31: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 32: Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
• 33: KAMGAR-PARSI, B. AND KANAL, L. N. 1985. An improved branch and bound algorithm for computing k -nearest neighbors. Pattern Recogn. Lett. 3, 1 (Jan.).
• 34: K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.166-176, June 01-04, 1998, Seattle, Washington, United States
• 35: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 36: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• 37: Hans-Peter Kriegel , Thomas Schmidt , Thomas Seidl, 3D Similarity Search by Shape Approximation, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.11-28, July 15-18, 1997
• 38: LINDENBAUM, M. AND SAMET, H. 1995. A probabilistic analysis of trie-based sorting of large collections of line segments. TR-3455. University of Maryland at College Park, College Park, MD.
• 39: David B. Lomet , Betty Salzberg, A Robust Multi-Attribute Search Structure, Proceedings of the Fifth International Conference on Data Engineering, p.296-304, February 06-10, 1989
• 40: M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
• 41: O J Murphy , S M Selkow, The efficiency of using k-d trees for finding nearest neighbors in discrete space, Information Processing Letters, v.23 n.4, p.215-218, Nov. 8, 1986 [doi>10.1016/0020-0190(86)90138-9]
• 42: Randal C. Nelson , Hanan Samet, A consistent hierarchical representation for vector data, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.197-206, Aug. 1986
• 43: BUREAU OF THE CENSUS, 1989. Tiger/Line precensus files. Bureau of the Census, Washington DC.
• 44: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 45: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 46: Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States
• 47: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 48: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 49: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 50: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 51: SPROULL, R. F. 1991. Refinements to nearest-neighbor searching in k-dimensional trees. Algorithmica 6, 4, 579-589.
• 52: UHLMANN, J. K. 1991. Satisfying general proximity/similarity queries with metric trees. Inf. Process. Lett. 40, 4 (Nov.), 175-179.
• 53: Tsong-Li Wang , Dennis Shasha, Query processing for distance metrics, Proceedings of the sixteenth international conference on Very large databases, p.602-613, September 1990, Brisbane, Australia
• 54: WHITE, D. A. AND JAIN, R. 1996. Algorithms and strategies for similarity retrieval. Tech. Rep. VCL-96-101. University of California at San Diego, La Jolla, CA.
• 55: David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

General Terms:
Algorithms, Performance

Keywords:
R-trees, distance browsing, hiearchical spatial data structures, nearest neighbors, ranking