摘要： 针对空间索引响应近邻查询效率低的问题,基于二进制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