Optimizing multidimensional index trees for main memory access

• Main Authors: Kim, Kihong, Cha, Sang K., Kwon, Keunjoo
• Format: Conference Proceeding
• Language: English
• Subjects: Computing methodologies > Artificial intelligence > Search methodologies; Computing methodologies > Artificial intelligence > Search methodologies > Discrete space search; Computing methodologies > Artificial intelligence > Search methodologies > Game tree search; Information systems > Data management systems > Data structures > Data access methods; Information systems > Information retrieval > Document representation; Information systems > Information retrieval > Search engine architectures and scalability > Search engine indexing; Information systems > Information storage systems > Record storage systems > Directory structures > B-trees; Mathematics of computing > Discrete mathematics > Graph theory > Trees
• ISSN: 0163-5808
• DOI: 10.1145/375663.375679

Recent studies have shown that cache-conscious indexes such as the CSB+-tree outperform conventional main memory indexes such as the T-tree. The key idea of these cache-conscious indexes is to eliminate most of child pointers from a node to increase the fanout of the tree. When the node size is chosen in the order of the cache block size, this pointer elimination effectively reduces the tree height, and thus improves the cache behavior of the index. However, the pointer elimination cannot be directly applied to multidimensional index structures such as the R-tree, where the size of a key, typically, an MBR (minimum bounding rectangle), is much larger than that of a pointer. Simple elimination of four-byte pointers does not help much to pack more entries in a node. This paper proposes a cache-conscious version of the R-tree called the CR-tree. To pack more entries in a node, the CR-tree compresses MBR keys, which occupy almost 80% of index data in the two-dimensional case. It first represents the coordinates of an MBR key relatively to the lower left corner of its parent MBR to eliminate the leading O's from the relative coordinate representation. Then, it quantizes the relative coordinates with a fixed number of bits to further cut off the trailing less significant bits. Consequently, the CR-tree becomes significantly wider and smaller than the ordinary R-tree. Our experimental and analytical study shows that the two-dimensional CR-tree performs search up to 2.5 times faster than the ordinary R-tree while maintaining similar update performance and consuming about 60% less memory space.