High Index Compression without the Dependencies of Data Orders and Data Skewness for Spatial Databases

摘要

The KDB-ttee and its variants have been reported to have good performance by using them as the index structures for retrieving multidimensional data. However, many literatures still frequently address the low storage utilization and insufficient retrieval performance as two bottlenecks for this family of structures. The excessive amount of frequent splits caused by improper data sequences and data skewness is the fatal reason for these two bottlenecks. Partition shifting (PS-method) and skewness handling (57/-method) proposed in this paper are proposed to conquer these problems. Without loss the quantity of data selectivity, a better dynamic partitioning scheme can accommodate data entries to leaves as many as possible. In addition, system performance degradation caused by skewed data is carefully investigated and our SH-method can prevent the well-classified pages from frequent splits. Analytical and experimental results show that both time and space efficiencies are significantly improved by the proposed compressed KDB-tiees.