OPTIMIZING STORAGE UTILIZATION AND INDEX REPRESENTATION IN KDB-TREE DYNAMIC INDEX STRUCTURE FOR HIGH DIMENSIONAL DATABASES

摘要

The splitting policy suffered from data insertion order is a fatal problem in a traditional KDB-tree and its variants. The conventional splitting strategies including forced splitting and first division splitting cause the low storage utilization, which increase the size of indexing structures and deteriorate the retrieval performance. In this paper, a new insertion algorithm with a new splitting strategy is proposed, which installs data as many as possible on the leaf nodes and the storage utilization is promoted to be almost 100%. In addition, the new entry representation eliminates redundant information from the internal structure in the high-dimensional spaces. The analytical and experimental results show that our indexing mechanism outperforms KDB-trees and its variants.