作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

基于Patricia树的空间索引结构

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

  1. (电子科技大学电子科学技术研究院,成都 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   

  1. (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

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

中图分类号: