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

The KDB-tree 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 (SH-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-trees.

並列關鍵字

KDB-trees ； index structures ； spatial databases ； partition shifting ； skewness handling

國際替代計量

全文下載

主題瀏覽