Keywords: KDB-trees, index structures, spatial databases, partition shifting, skewness handling
Received April 21, 2009; revised September 11 & November 16, 2009; accepted January 5, 2010.
Communicated by Tei-Wei Kuo.
| 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] |
¡@
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.
Received April 21, 2009; revised September 11 & November 16, 2009; accepted January 5, 2010.
Communicated by Tei-Wei Kuo.