Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Modern database applications like geographic information systems, multimedia databases, and digital libraries dealing with huge volumes of high dimensional data, make use of multidimensional index structures. Among them, SR-tree has been shown to outperform the R-Tree and its variants and the SS-Tree. For static datasets, packed index structures provide better retrieval performance. This paper presents schemes for SR-Tree packing based on different pre-processing techniques. The results show that these schemes consistently outperform packed R-Tree and conventional SR-Tree structures in terms of storage space and query performance.

REFERENCES

• 1: T. Bially. Space-Filling Curves: Their Generation and Their Application to Bandwidth Reduction. IEEE Transactions on Information Theory, 15(6):658--664, 1969.
• 2: 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
• 3: 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
• 4: 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
• 5: Scott T. Leutenegger , Jeffrey M. Edgington , Mario A. Lopez, STR: A simple and efficient algorithm for R-tree packing, Institute for Computer Applications in Science and Engineering (ICASE), 1997
• 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: H. Sagan. Space-Filling Curves. Springer Verlag, New York, NY, USA, 1994.
• 8: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 9: 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.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Performance