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 Proceedings of the ACM SIGMOD International Conference on the Management of Data, 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 Proceedings of the ACM SIGMOD International Conference on the Management of Data, 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 Proceedings of the ACM PODS Symposium on Principles of Database Systems, 1997.
4. S. Berchtold, D. A. Keim, and Hans-Peter Kriegel. The X-tree: an index structure for high-dimensional data. In Proceedings of the 22nd International Conference on VLDB, 1996.
5. S. Brin. Near neighbor search in large metric space. In Proceedings of the 21st International Conference on VLDB, pages 574-584. 1995.
6. A. Brink, S. Marcus, and V. S. Subrahmanian. Heterogeneous Multimedia Reasoning. IEEE Computer, 28(9), September 1995.
7. Tzi-cker Chiueh. Content-based image indexing. In Proceedings of the 20th VLDB Conference, 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. IEEE Computer, 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. ACM Transactions on Mathematical Software, 3(3):209-226, September 1977.
10. A. Guttman. R-trees: a dynamic index structure for spatial searching. In Proceedings of the ACM SIGMOD International Conference on the Management of Data, 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 Proceedings of ACM SIGMOD, 1995.
12. King-ip Lin, H. V. Jagadish, and C. Faloutsos. The TV-tree - an index structure for high-dimensional data. VLDB Journal, 3:517-542, October 1994.
13. V. E. Ogle. "Chabot: Retrieval from a Relational Database of Images. IEEE Computer, 28(9), September 1995.
14. N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proceedings of the ACM SIGMOD International Conference on the Management of Data, pages 71-79, June 1995.
15. H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1989.
16. T. Sellis, N. Roussopoulos, and C. Faloutsos. The R<sup>+</sup>-tree: a dynamic index for multidimensional objects. In Proceedings of the 13th International Conference on VLDB, pages 507-518. 1987.
17. D. A. White and R. Jain. Similarity indexing with the SS-tree. In Proceedings of the 12th IEEE International Conference on Data Engineering, pages 516-523, February 1996.

Index Terms

• Information systems

  • Information retrieval

    • Document representation

    • Information retrieval query processing

    • Search engine architectures and scalability

      • Search engine indexing