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

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

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

Full Text: PDF(467.9KB)

Summary: 
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.