A Spatial Distribution Pattern-driven Spatial Index

doi:10.11947/j.AGCS.2015.20130245

Abstract

Abstract: Packing spatial data into blocks and processing of global impact of local operations are two important tasks for spatial index to support bulk operations. In this paper, we present a new spatial index called Pattern-tree for bulk operations with spatial distribution pattern analysis. For packing objects into blocks, a new spatial data partitioning method based on the detection of the spatial distribution pattern was presented. This paper introduces a novel spatial index construction algorithm that combines of top-down and bottom-up methods; For processing of local update operations and its global impact, this paper introduces a new algorithm based on change analysis of the spatial distribution pattern. Empirical results demonstrate that performance improvements are achieved in practice in the case of spatial index construction and windows query compared with STLT, GBI and SCB.

Key words: spatial index, bulk operations, spatial distribution pattern

CLC Number:

P208

WU Mingguang. A Spatial Distribution Pattern-driven Spatial Index[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(1): 108-115.

References

[1] WANG Yanmin, GUO Ming. A Combined 2D and 3D Spatial Indexing of Very Large Point-cloud Data Sets[J].Acta Geodaetica et Cartographica Sinica,2012,41(4):605-612.(王晏民,郭明.大规模点云数据的二维与三维混合索引方法[J].测绘学报,2012,41(4):605-612.)
[2] AGHBARI Z A. CTraj: Efficient Indexing and Searching of Sequences Containing Multiple Moving Objects[J]. Journal of Intelligent Information Systems, 2012, 39 (1): 1-28.
[3] GARCIA Y, LOPEZ M, LEUTENEGGER S T. A Greedy Algorithm for Bulk Loading R-trees[C]//Proceedings of the 6th ACM-GIS.Washington DC:[s.n.],1998:163-164.
[4] LEE T, LEE S. OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree[C]//Advanced Information Systems Engineering. Klagenfurt:[s.n.],2003: 69-72.
[5] CHEN L, CHOUBEY R, RUNDENSTEINER E A. Merging R-Trees: Efficient Strategies for Local Bulk Insertion[J]. Geoinformatica, 2002, 6(1): 7-34.
[6] CHOUBEY R, CHEN L, RUNDENSTEINER E A. GBI: A Generalized R-tree Bulk-insertion Strategy[C]//Proceedings of SSD.Hong Kong:[s.n.],1999:91-108.
[7] LEE T, MOON B, LEE S. Bulk Insertion for R-tree by Seeded Clustering[C]//Database and Expert Systems Applications.Prague:[s.n.],2003:129-138.
[8] GONG Jun,ZHU Qing,ZHANG Yeting,et al. An Efficient 3D R-tree Extension Method Concerned with Levels of Detail[J]. Acta Geodaetica et Cartographica Sinica,2011,40(2):249-255. (龚俊,朱庆,张叶廷,等.顾及多细节层次的三维R树索引扩展方法. 测绘学报,2011,40(2):249-255.)
[9] BERCKEN J, SEEGER B, WIDMAYER P. A Generic Approach to Bulk Loading Multidimensional Index Structures[C]//Proceedings of the 23rd VLDB.Athens:[s.n.],1997:406-415.
[10] ROUSSOPOULOS N, LEIFKER D. Direct Spatial Search on Pictorial Databases Using Packed R-trees[C]//Proceedings of ACM SIG-MOD.Austin:[s.n.],1985:17-31.
[11] KAMEL I, FALOUTSOS C. On Packing R-trees[C]//Proceedings of CIKM. Washington DC:[s.n.],1993: 490-499.
[12] CHEN L, CHOUBEY R, RUNDENSTEINER E A. Bulk-insertions into R-trees Using the Small-tree-large-tree Approach[C]//Proceedings of ACM-GIS. Washington DC:[s.n.],1998:161-162.
[13] GAVRILA D M. R-tree Index Optimization[C]//Proceedings of the Sixth International Symposium on Spatial Data Handling. Edinburgh:[s.n.],1994:771-791.
[14] SHEKHAR S, RAVADA S, KUMAR V. Declustering and Load-balancing Methods for Paralleling Geographic Information Systems[J]. IEEE Transactions on Knowledge and Data Engineering, 1998,10(4):632-655.
[15] MOON B, JAGADISH H V, FALOUTSOS C. Analysis of the Clustering Properties of the Hilbert Space-filling Curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001,13: 124-141.
[16] SAMET H. Hierarchical Representation of Collections of Small Rectangles[J]. ACM Computing Surveys, 1998,20 (4): 271-309.
[17] GUTTMAN A. R-trees: a Dynamic Index Structure for Spatial Searching[C]//Proceedings of ACM SIGMOD International Conference on Management of Data. Boston:[s.n.],1984:47-57.
[18] BENTLEY J L, FRIEDMAN J H. Data Structures for Range Searching[J]. ACM Computing Surveys,1979, 11 (4): 397-409.
[19] WANG Yuanfei, HE Honglin. Spatial Data Analysis[M].Beijing:Science Press,2007. (王远飞, 何洪林. 空间数据分析方法[M].北京:科学出版社,2007.)
[20] ZHOU Yan, ZHU Qing, ZHANG Yeting. A Spatial Data Partitioning Algorithm Based on Spatial Hierarchical Decomposition Method of Hilbert Space-filling Curve[J]. Geography and Geo-Information Science,2007,23(4):13-17. (周燕,朱庆,张叶廷.基于Hilbert曲线层次分解的空间数据划分方法[J]. 地理与地理信息科学,2007,23(4):13-17.)
[21] LU Feng, ZHOU Chenghu. A GIS Spatial Indexing Approach Based on Hilbert Ordering Code[J]. Journal of Computer-Aided Design & Computer Graphics, 2001,13(5):424-429. (陆锋,周成虎.一种基于Hilbert排列码的GIS空间索引方法[J].计算机辅助设计与图形学学报,2001,13(5):424-429.)