The Optimization of In-Memory Space Partitioning Trees for Cache Utilization

Myung Ho YEO  Young Soo MIN  Kyoung Soo BOK  Jae Soo YOO  

IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.2   pp.243-250
Publication Date: 2008/02/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.2.243
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Database
cache conscious,  in-memory,  index structure,  KDB-tree,  

Full Text: PDF>>
Buy this Article

In this paper, a novel cache conscious indexing technique based on space partitioning trees is proposed. Many researchers investigated efficient cache conscious indexing techniques which improve retrieval performance of in-memory database management system recently. However, most studies considered data partitioning and targeted fast information retrieval. Existing data partitioning-based index structures significantly degrade performance due to the redundant accesses of overlapped spaces. Specially, R-tree-based index structures suffer from the propagation of MBR (Minimum Bounding Rectangle) information by updating data frequently. In this paper, we propose an in-memory space partitioning index structure for optimal cache utilization. The proposed index structure is compared with the existing index structures in terms of update performance, insertion performance and cache-utilization rate in a variety of environments. The results demonstrate that the proposed index structure offers better performance than existing index structures.