Enhanced nearest neighbour search on the R-tree

ABSTRACT

Multimedia databases usually deal with huge amounts of data and it is necessary to have an indexing structure such that efficient retrieval of data can be provided. R-Tree with its variations, is a commonly cited indexing method. In this paper we propose an improved nearest neighbor search algorithm on the R-tree and its variants. The improvement lies in the removal of two hueristics that have been used in previous R*-tree work, which we prove cannot improve on the pruning power during a search.

REFERENCES

• 1: N. Beckmann, Hans-Peter Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In <i>Proceedings of the ACM SIGMOD International Conference on the Management of Data,</i> pages 322-331, May 1990.
• 2: S. Berchtold, C. Bohm, B. Braunmuller, D. Keim, and H. P. Kriegel. Fast Parallel Similarity Search in Multimedia Databases. In <i>Proceedings of the ACM SIGMOD International Conference on the Management of Data,</i> 1997.
• 3: S. Berchtold, C. Bohm, D. Keim, and H. P. Kriegel. A Cost Model for Nearest Neighbor Search in High Dimensional Data Space. In <i>Proceedings of the ACM PODS Symposium on Principles of Database Systems,</i> 1997.
• 4: S. Berchtold, D. A. Keim, and Hans-Peter Kriegel. The X-tree: an index structure for high-dimensional data. In <i>Proceedings of the 22nd International Conference on VLDB,</i> 1996.
• 5: S. Brin. Near neighbor search in large metric space. In <i>Proceedings of the 21st International Conference on VLDB,</i> pages 574-584. 1995.
• 6: A. Brink, S. Marcus, and V. S. Subrahmanian. Heterogeneous Multimedia Reasoning. <i>IEEE Computer,</i> 28(9), September 1995.
• 7: Tzi-cker Chiueh. Content-based image indexing. In <i>Proceedings of the 20th VLDB Conference,</i> pages 582-593, 1994.
• 8: M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by image and video content: the QBIC system. <i>IEEE Computer,</i> 28(9):23-32, September 1995.
• 9: J. H. Friedman, J. L. Bentley, and R. A. Finkel. An Algorithm for Finding Best Matches in Logarithmic Expected Time. <i>ACM Transactions on Mathematical Software,</i> 3(3):209-226, September 1977.
• 10: A. Guttman. R-trees: a dynamic index structure for spatial searching. In <i>Proceedings of the ACM SIGMOD International Conference on the Management of Data,</i> pages 47-57, June 1984.
• 11: King-ip Lin and C. Faloutsos. Fastmap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In <i>Proceedings of ACM SIGMOD,</i> 1995.
• 12: King-ip Lin, H. V. Jagadish, and C. Faloutsos. The TV-tree - an index structure for high-dimensional data. <i>VLDB Journal,</i> 3:517-542, October 1994.
• 13: V. E. Ogle. "Chabot: Retrieval from a Relational Database of Images. <i>IEEE Computer,</i> 28(9), September 1995.
• 14: N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In <i>Proceedings of the ACM SIGMOD International Conference on the Management of Data,</i> pages 71-79, June 1995.
• 15: H. Samet. <i>The Design and Analysis of Spatial Data Structures.</i> Addison-Wesley, 1989.
• 16: T. Sellis, N. Roussopoulos, and C. Faloutsos. The R⁺-tree: a dynamic index for multidimensional objects. In <i>Proceedings of the 13th International Conference on VLDB,</i> pages 507-518. 1987.
• 17: D. A. White and R. Jain. Similarity indexing with the SS-tree. In <i>Proceedings of the 12th IEEE International Conference on Data Engineering,</i> pages 516-523, February 1996.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Performance