基于Patricia树的空间索引结构

• 作者: 刘丹 张可 徐展 易显天 郭承军
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: Patricia树 Morton码 近邻搜索 空间索引 区域查询
• 年，卷（期）: 2015,（12）
• 所属期刊栏目: 先进计算与数据处理
• 页码范围: 69-74
• 页数: 6页
• 分类号: TP392
• 字数: 4250字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2015.12.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭承军	电子科技大学电子科学技术研究院	62	236	8.0	13.0
2	张可	电子科技大学电子科学技术研究院	33	182	8.0	11.0
3	易显天	电子科技大学电子科学技术研究院	2	8	2.0	2.0
4	徐展	电子科技大学电子科学技术研究院	7	61	5.0	7.0
5	刘丹	电子科技大学电子科学技术研究院	50	231	8.0	12.0