An efficient cache conscious multi-dimensional index structure

ABSTRACT

Recently, to relieve the performance degradation caused by the bottleneck between CPU and main memory, cache conscious multi-dimensional index structures have been proposed. The ultimate goal of them is to reduce the space for entries so as to widen index trees and minimize the number of cache misses. The existing index structures can be classified into two approaches according to their entry reduction methods. One approach is to compress MBR keys by quantizing coordinate values to the fixed number of bits. The other approach is to store only the sides of minimum bounding regions (MBRs) that are different from their parents partially. The second approach works well when the size of a node is small and the number of entries is small. In this paper, we investigate the existing multi-dimensional index structures for main memory database systems through experiments under the various work loads. Then, we propose a new index structure that exploits the properties of the both techniques. We implement existing multi-dimensional index structures and the proposed index structure. We perform various experiments to show that our approach outperforms others.

REFERENCES

• 1: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , David A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the 25th International Conference on Very Large Data Bases, p.266-277, September 07-10, 1999
• 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: {3} http://icl.cs.utk.edu/papi/index.html.
• 4: {4} http://www.cs.du.edu/~leut/MultiDimData.html.
• 5: Inga Sitzmann , Peter J. Stuckey, Compacting discriminator information for spatial trees, Proceedings of the thirteenth Australasian database conference, p.167-176, January 01, 2002, Melbourne, Victoria, Australia
• 6: Jun Rao , Kenneth A. Ross, Cache Conscious Indexing for Decision-Support in Main Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.78-89, September 07-10, 1999
• 7: Jun Rao , Kenneth A. Ross, Making B+- trees cache conscious in main memory, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.475-486, May 15-18, 2000, Dallas, Texas, United States
• 8: Kihong Kim , Sang K. Cha , Keunjoo Kwon, Optimizing multidimensional index trees for main memory access, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.139-150, May 21-24, 2001, Santa Barbara, California, United States
• 9: Philip Bohannon , Peter Mcllroy , Rajeev Rastogi, Main-memory index structures with fixed-size partial keys, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.163-174, May 21-24, 2001, Santa Barbara, California, United States
• 10: Scott T. Leutenegger , J. M. Edgington , Mario A. Lopez, STR: A Simple and Efficient Algorithm for R-Tree Packing, Proceedings of the Thirteenth International Conference on Data Engineering, p.497-506, April 07-11, 1997
• 11: Shimin Chen , Phillip B. Gibbons , Todd C. Mowry, Improving index performance through prefetching, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.235-246, May 21-24, 2001, Santa Barbara, California, United States
• 12: Stefan Manegold , Peter A. Boncz , Martin L. Kersten, Optimizing database architecture for the new bottleneck: memory access, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.231-246, December 2000 [doi>10.1007/s007780000031]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

General Terms:
Algorithms, Performance

Keywords:
MBR, cache, data structures, main-memory database, multi-dimensional index structure, performance evaluation