支持批量操作的空间索引中,空间数据的分解粒度、局部更新操作的整体影响处理是两个主要难点.本文基于空间分布模式分析,提出了一种空间索引—— Pattern-tree.针对批量操作的粒度问题,设计了一种基于空间分布模式探测的空间划分方法,采用一种自上而下与自下而上相结合的索引树构建算法;针对局部插入操作对索引树的整体影响与索引树的调整问题,提出了一种基于空间分布模式变化检测的索引更新方法.试验表明,本文所提出的空间索引结构比STLT、GBI以及SCB等方法具有更高的构建与窗口查询效率.
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.
[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.)
