基于Patricia树的空间索引结构

doi:10.3969/j.issn.1000-3428.2015.12.014

计算机工程

基于Patricia树的空间索引结构

易显天,徐展,郭承军,刘丹,张可

(电子科技大学电子科学技术研究院,成都 611731)

收稿日期:2014-12-26 出版日期:2015-12-15 发布日期:2015-12-15
作者简介:易显天(1989－),男,硕士,主研方向:空间数据库技术;徐展,高级工程师、硕士;郭承军,博士;刘丹,副教授、博士;张可,副研究员、博士。
基金项目:
宁波市重点科技攻关计划基金资助项目(2011C51007)。

Spatial Index Structure Based on Patricia Tree

YI Xiantian,XU Zhan,GUO Chengjun,LIU Dan,ZHANG Ke

(Research Institute of Electronic Science and Technology,University of Electronic Science and Technology of China,Chengdu 611731,China)

Received:2014-12-26 Online:2015-12-15 Published:2015-12-15

摘要/Abstract

摘要： 针对空间索引响应近邻查询效率低的问题,基于二进制Morton码和Patricia树,提出一种一维空间索引结构。通过改良Patricia树结构及其相关算法提高索引结构的操作效率。基于Morton码特点,融合索引结构和Morton码,使得索引结构拥有高效响应近邻查询的能力,并同时提出基于MPT的近邻算法。将二维空间进行预定规则下的不同粒度的划分,把分块后的二维空间区域转换为一维编码,使MPT索引具备高效响应区域查询能力。分析区域查询误差出现的原因,并给出相应解决方案。实验结果表明,与B+树、Hash表、Trie树相比,该方法在查询速度上更具优势,基于MPT的近邻搜索比基于R-Tree近邻搜索效率更高。

关键词: Patricia树, Morton码, 近邻搜索, 空间索引, 区域查询

Abstract: Aiming at low efficiency problem of spatial index that answers nearest neighbor query and other kind of query,this paper proposes an index structure called Morton Patricia Tree(MPT) which is based on Patricia tree and binary Morton code.It improves the efficiency of MPT index structure by reforming structure of patricia tree and relative algorithm.Based on the characteristics of Morton code,it integrates index structure and binary Morton code to meet the need of neighbor query,and proposes the nearest neighbor search algorithm based on MPT at the same time.MPT gains the capability of region query by dividing the two-dimensional space into different size cubes according to predefined rules and converting each cube into Morton code.The paper analyzes the reason why range query error occurs and puts forward the solution.Experimental result shows that the search speed of MPT index structure is faster than that of B+tree,Hash table and trie tree.The nearest neighbor query based on MPT is more efficient than that based on R-Tree.

Key words: Patricia tree, Morton code, neighbor search, spatial index, region query

中图分类号:

TP392

易显天,徐展,郭承军,刘丹,张可. 基于Patricia树的空间索引结构[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2015.12.014.

YI Xiantian,XU Zhan,GUO Chengjun,LIU Dan,ZHANG Ke. Spatial Index Structure Based on Patricia Tree[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2015.12.014.

参考文献

参考文献［1］廖巍,熊伟,景宁.移动对象索引技术研究进展［J］.计算机科学,2006,33(8):166-169. ［2］孟小峰,周龙骧,王珊.数据库技术发展趋势［J］.软件学报,2004,15(12):1822-1836. ［3］Jensen C S,Lin Dan,Ooi B C.Query and Update Efficient B+-tree Based Indexing of Moving Objects［C］//Proceedings of the 30th International Conference on Very Large Data Bases.［S.1.］:VLDB Endowment,2004:768-779. ［4］Su Chen,Ooi B C,Tan K L,et al.ST2B-tree:A Self-tunable Spatio-temporal B+-tree Index for Moving Objects［C］//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2008:29-42. ［5］刘玥,郝忠孝.基于 Buddy*-Hash 的移动对象时空查询方法［J］.计算机工程,2010,36(4):47-49. ［6］Tao Yufei,Papadias D,Sun Jimeng.The TPR*-tree:An Optimized Spatio-temporal Access Method for Predictive Queries［C］//Proceedings of the 29th International Conference on Very Large Data Bases.［S.1.］:VLDB Endowment,2003:790-801. ［7］Simonas S C S J,Leutenegger S T,Lopez M A.Indexing the Positions of Continuously Moving Objects［C］//Proceedings of SIGMOD’00.New York,USA:ACM Press,1999:331-342. ［8］徐红波,郝忠孝.基于Hilbert曲线的近似k-最近邻查询算法［J］.计算机工程,2008,34(12):47-49. ［9］刘润涛,陈琳琳,田广悦,等.Z曲线网格划分的最近邻查询［J］.计算机工程与应用,2013,49(22):123-126. ［10］徐红波,郝忠孝.基于空间填充曲线网格划分的最近邻查询算法［J］.计算机科学,2010,37(1):184-188. ［11］Liu Jiajun,Li Haoran,Yong Gao et al.A Geohash-based Index for Spatial Data Management in Distributed Memory［C］//Proceedings of the 22nd International Conference on Geoinformatics.Washington D.C.,USA:IEEE Press,2014:1-4. ［12］Brinkhoff T.Generating Network-based Moving Objects［C］//Proceedings of the 22nd International Conference on Scienti-fic and Statistical Database Management.Washington D.C.,USA:IEEE Press,2000:253-255. 编辑索书志

[1]	杨雪,范勇,高琳,邱运春. 基于纹理基元块识别与合并的图像语义分割[J]. 计算机工程, 2015, 41(3): 253-257.
[2]	杨定中,陈心浩. 基于投影残差量化哈希的近似最近邻搜索[J]. 计算机工程, 2015, 41(12): 161-165,170.
[3]	梁轲,谭建军,李英远. 一种基于MapReduce的短时交通流预测方法[J]. 计算机工程, 2015, 41(1): 174-179.
[4]	李松,张丽平,刘艳,郝晓红,杨和禹. 障碍物环境下的动态单纯型连续近邻链查询[J]. 计算机工程, 2014, 40(8): 52-57.
[5]	吴勇，罗腾元，王美珍. 可定位图像采集与检索方法研究[J]. 计算机工程, 2014, 40(7): 207-211,220.
[6]	赵龙，闵世平，代强玲. 基于八叉树的三维地质剖面生成算法[J]. 计算机工程, 2014, 40(2): 250-255.
[7]	赵景昌,白润才,刘光伟,刘威. 基于空间索引与碰撞检测的TIN求交算法[J]. 计算机工程, 2014, 40(12): 296-301.
[8]	赵艳伟, 程振林, 董慧, 方金云. 一种用于网络地图的栅格索引技术[J]. 计算机工程, 2011, 37(2): 27-29.
[9]	马慧, 吴凌坤. 一种用于多属性范围查询的聚簇方法[J]. 计算机工程, 2011, 37(19): 41-43,46.
[10]	李峰, 蔡琼. 基于SIFT的图像盲取证方法[J]. 计算机工程, 2011, 37(14): 233-235.
[11]	邹志文, 费洪哲, 李根. 基于聚类的空间数据多比例尺索引树[J]. 计算机工程, 2011, 37(14): 56-58.
[12]	李建勋, 沈冰, 姜仁贵, 陈田庆. 面向影像金字塔的四叉树空间索引算法[J]. 计算机工程, 2011, 37(10): 11-13.
[13]	彭勤生;方金云;张娟. 基于空间和属性数据的联合索引技术[J]. 计算机工程, 2010, 36(8): 71-73.
[14]	孙晓明, 吉根林. 基于QR树索引的面包含关系求解算法[J]. 计算机工程, 2010, 36(21): 37-39.
[15]	马捷, 李岩, 董学敏. XML-enabled空间数据库的索引系统[J]. 计算机工程, 2010, 36(13): 48-50,53.

基于Patricia树的空间索引结构

Spatial Index Structure Based on Patricia Tree

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10