基于Patricia树的空间索引结构

摘要：

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

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

所属期刊栏目：41

分类号：TP392(计算技术、计算机技术)

资助基金：宁波市重点科技攻关计划基金资助项目2011C51007

在线出版日期：2016-02-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：69-74