Realization of R-tree for GIS on hybrid clustering algorithm

Abstract

The characteristic of geographic information system (GIS) spatial data operation is that query is much more frequent than insertion and deletion, and a new hybrid spatial clustering method used to build R-tree for GIS spatial data was proposed in this paper. According to the aggregation of clustering method, R-tree was used to construct rules and specialty of spatial data. HCR-tree was the R-tree built with HCR algorithm. To test the efficiency of HCR algorithm, it was applied not only to the data organization of static R-tree but also to the nodes splitting of dynamic R-tree. The results show that R-tree with HCR has some advantages such as higher searching efficiency, less disk accesses and so on.

Keywords

R-tree / HCR algorithm / multi-dimension spatial objects / spatial clustering / GIS

References

[1] ZhuTie-wenThe Key Techniques of Spatial Data-base based on Regularly Spatial Discrete Domains Objects[D], 2002, Changsha, Institute of Electrical Science and Engineering, National University of Defence Technology(in Chinese)

[2] GuttmanATormarkB. R-tree: A dynamic index structure for spatial searching[A]. Proceedings of 13th ACM SIGMOD International Conference on Management of Data[C], 1984, New York, NY, USA, ACM Press: 47-57

[3] KamelI, FaloutsosCBhargavaB K, FininT W, YeshaY. On Packing R-trees[A]. Proceedings of 2nd International Conference on Data Engineering[C], 1993, New York, NY, USA, ACM Press: 490-499

[4] SellisT, RoussopoulosN, FaloutsosCStockerP M, KentW, HammersleyP. The R⁺-Tree: A Dynamic Index for Mult1-dimensional Objects [A]. VLDB’87[C], 1987, Brighton, England, Morgan Kanfonann: 507-518

[5] BeckmannN, KriegelH P, SchneiderR, et al.. The R^#-tree: an efficient and robust access method for points and rectangles[A]. Proceedings 1990 ACM SIGMOD Conference [C], 1990, New York, NY, USA, ACM Press: 322-331

[6] Kamel I. Hilbert R-tree: An Improved R-tree Using Fractals[A]. Bocca J B, Jarke M, Zaniolo C, ed. Proceedings of the 20th VLDB Conference[C]. Morgan Kaufmann, 1994. 50–509.

[7] BrakatsoulasS, PfoserD, TheodoridisYManolopoulosY, NávratP. Revisiting R-tree construction principles[A]. 6th East-European Conference on Advances in Databases and Information Systems[C], 2002, London, Springer-Verlag: 149-162

[8] SchreckT, ChenZ. Branch grafting method for R-tree implementation[J]. The Journal of Systems and Software, 2000, 53(1): 83-93 in Chinese)

[9] HuangP W, LinP L, LinH Y. Optimizing storage utilization in R-tree dynamic index structure for spatial database[J]. The Journal of Systems and Software, 2001, 55(3): 291-299 in Chinese)

[10] Yazdani Z, Ozsoyoglu M. A framework for feature-based indexing in spatial database[A]. French J C, Hinterberger H, ed. 7th International Working Conference on Scientific and Statistical Database Management[C]. IEEE Computer Society, 1994, 259–269.

[11] OlgaS, BoeyS H. Geometric query types for data retrieval in relational databases[J]. Data & Knowledge Engineering, 1998, 27(2): 207-229

[12] ChengShengThe research of GIS Spatial Database Foundational Technique[D], 1998, Changsha, Institute of Electrical Science and Engineering, National University of Defence Technology

[13] GuoRen-zhongSpatial Analysis[M], 2000, Wuhan, Wuhan Technical University of Surveying and Mapping Press

[14] VrahatisM N. The new k-windows algorithm for improving the k-means clustering algorithm[J]. Journal of Complexity, 2002, 18(1): 375-391