一种空间分布模式驱动的空间索引

doi:10.11947/j.AGCS.2015.20130245

测绘学报 ›› 2015, Vol. 44 ›› Issue (1): 108-115.doi: 10.11947/j.AGCS.2015.20130245

一种空间分布模式驱动的空间索引

吴明光

南京师范大学虚拟地理环境教育部重点实验室, 江苏南京 210023

收稿日期:2014-01-02 修回日期:2014-08-16 出版日期:2015-01-20 发布日期:2015-01-22
作者简介:吴明光(1979-), 男, 副教授, 主要研究方向为空间数据模型、空间信息可视化、空间信息服务等. E-mail: wmg@njnu.edu.cn
基金资助:
国家自然科学基金(41271446;41271384)

A Spatial Distribution Pattern-driven Spatial Index

WU Mingguang

Key Laboratory of Virtual Geographic Environment of Ministry of Education, Nanjing Normal University, Nanjing 210023, China

Received:2014-01-02 Revised:2014-08-16 Online:2015-01-20 Published:2015-01-22
Supported by:
The National Natural Science Foundation of China(Nos.41271446 41271384)

摘要/Abstract

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

关键词: 空间索引, 批量操作, 空间分布模式

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

中图分类号:

P208

吴明光. 一种空间分布模式驱动的空间索引[J]. 测绘学报, 2015, 44(1): 108-115.

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

参考文献

[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.)

一种空间分布模式驱动的空间索引

A Spatial Distribution Pattern-driven Spatial Index

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价

[1]	刘慧敏, 胡文柯, 唐建波, 石岩, 邓敏. 顾及功能语义特征的建筑物空间分布模式识别方法[J]. 测绘学报, 2020, 49(5): 622-631.
[2]	吴政, 武鹏达, 李成名. 对等网络下自适应层级的矢量数据时空索引构建方法[J]. 测绘学报, 2019, 48(11): 1369-1379.
[3]	赖广陵, 童晓冲, 丁璐, 秦志远. 三维空间格网的多尺度整数编码与数据索引方法[J]. 测绘学报, 2018, 47(7): 1007-1017.
[4]	曹雪峰, 万刚, 张宗佩. 紧致的Hilbert曲线Gray码索引算法[J]. 测绘学报, 2016, 45(S1): 90-98.
[5]	李振豪, 杨春成, 魏斌, 周校东, 何列松, 信睿. 道路与建筑物空间冲突的几何相似性移位算法[J]. 测绘学报, 2016, 45(6): 747-755.
[6]	唐建波, 刘启亮, 邓敏, 黄金彩, 蔡建南. 空间层次聚类显著性判别的重排检验方法[J]. 测绘学报, 2016, 45(2): 233-240.
[7]	付仲良, 胡玉龙, 翁宝凤, 彭瑞. M-Quadtree索引:一种基于改进四叉树编码方法的云存储环境下空间索引方法[J]. 测绘学报, 2016, 45(11): 1342-1351.
[8]	段红伟孟令奎黄长青李颖李继园 . 基于SPARQL查询的地理语义空间索引构建方法[J]. 测绘学报, 2014, 43(2): 193-199.
[9]	王晏民,郭明. 大规模点云数据的二三维混合索引方法[J]. 测绘学报, 2012, 41(4): 0-590.
[10]	龚俊,朱庆,张叶廷,李晓明,周东波. 顾及多细节层次的三维R树索引扩展方法[J]. 测绘学报, 2011, 40(2): 249-255.