A New R*Q-tree Spatial Index based on the Delaying Selection and Clustering Splitting

Full Text (PDF, 137KB), PP.40-46

Views: 0 Downloads: 0

Author(s)

Quanyou Song 1,* Wan-gao Li 2

1. Henan Vocational and Technical College of Communications, Zhengzhou, China

2. Henan Institute of Engineering, Zhengzhou, China

* Corresponding author.

DOI: https://doi.org/10.5815/ijwmt.2011.04.06

Received: 7 Apr. 2011 / Revised: 17 May 2011 / Accepted: 5 Jul. 2011 / Published: 15 Aug. 2011

Index Terms

Delaying Selection Splitting, Clustering Splitting, R*Q-tree

Abstract

The original R*Q-tree is an important class of query index in the spatial database, but when carry on frequent insertion and deletion, the efficiency is very low, because its construction cost is much more than that of the other query methods. So the new R*Q-tree using the delaying and Clustering splitting technology has been proposed for improving the shortcomings of the original R*Q-tree. When the data objects are inserted into the new R*Q-tree, the nodes may overflow. During the process of insertion, rather than split the node immediately, it attempts to insert the nodes into the adjacent neighboring nodes by using of the delaying selection splitting technology until they are full. If the adjacent neighboring nodes are full, it will use the clustering technology to split the nodes, data items will be reorganized between the neighboring nodes and the splitted nodes. The new R*Q-tree can ensure the premise of the query performance and the cost of structure greatly reduced, at the same time, significantly the space utilization of the index structure is improved. Finally, the experimental analysis and appraisals show that the operation efficiency of the new R*Q-tree is enhanced. And in the new R*Q-tree and the promoter region, there are no duplicated elements, so the structure of the new R*Q-tree can be simplified.

Cite This Paper

Quanyou Song, Wan-gao Li,"A New R*Q-tree Spatial Index based on the Delaying Selection and Clustering Splitting", IJWMT, vol.1, no.4, pp.40-46, 2011. DOI: 10.5815/ijwmt.2011.04.06 

Reference

[1] A.Guttman, “R-trees: A Dynamic Index Structure for Spatial Searching,” Proc. ACM SIGMOD, 1984, pp.47–57.

[2] Shupeng Chen, Xuejun Lu, Chenghu Zhou, “Geography informational system,” Beijing science press, 1999. (in chinese)

[3] Guobin Li,Yongli Tang, “Spatial database technology,” Electronics industry press, 2009. (in chinese)

[4] Xiaofeng Lei, Kunqing Xie, Xingxing Jin, “A Novel Implementation of Dynamic n R-tree Based on Lazy Splitting and Clustering,” Computer Science, Vol.34, No 4, 2007, pp.102–125.

[5] Ming Huang, Zhe Chen, “Research on the spatial index based on improvement RQ-tree,” Journal of Heilongjiang Institute of Technology, Vol.19, No3, 2005, pp.18–20.

[6] Xincai Wu, “Geography informational system theory and method,” Electronics industry press, 2009. (in chinese)

[7] Jianhua Qiu, Xuebing Tang, Huaguo Huang, “An index structure based on quad-tree and R*-tree–R*Q-tree,” Computer applications, Vol.23, NO.8, 2003, pp. 124–126