Spatial Index Structure Based on Patricia Tree
YI Xiantia · Jisuanji gongcheng · 2015
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.