Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24] [ 25]

@

Journal of Information Science and Engineering, Vol. 27 No. 2, pp. 561-576 (March 2011)

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

HUNG-YI LIN
Department of Distribution Management
National Taichung Institute of Technology
Taichung, 404 Taiwan
E-mail: linhy@ntit.edu.tw

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.

Keywords: KDB-trees, index structures, spatial databases, partition shifting, skewness handling

Full Text () Retrieve PDF document (201103_11.pdf)

Received April 21, 2009; revised September 11 & November 16, 2009; accepted January 5, 2010.
Communicated by Tei-Wei Kuo.