多维空间索引结构SHG-Tree

doi:10.3778/j.issn.1673-9418.2009.01.007

计算机科学与探索 ›› 2009, Vol. 3 ›› Issue (1): 68-90.DOI: 10.3778/j.issn.1673-9418.2009.01.007

多维空间索引结构SHG-Tree

刘胤田^1,2,刘应明¹,徐开阔³,曾涛⁴,唐常杰³⁺

1. 四川大学数学学院，成都 610065
2. 成都信息工程学院数据库与知识工程实验室，成都 610225
3. 四川大学计算机学院，成都 610065
4. 天津师范大学计算机与信息工程学院，天津 300074

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-01-20 发布日期:2009-01-20
通讯作者: 唐常杰

SHG-Tree： An Efficient Index Structure of Spatial Database

LIU Yintian^1,2, LIU Yingming¹, XU Kaikuo³, ZENG Tao⁴, TANG Changjie³⁺

1. College of Mathematics， Sichuan University， Chengdu 610065， China
2. Lab of Database and Knowledge Engineering， Chengdu University of Information Technology， Chengdu 610225， China
3. College of Computer Science， Sichuan University， Chengdu 610065， China
4. College of Computer and Information Engineering， Tianjin Normal University， Tianjin 300074， China

Received:1900-01-01 Revised:1900-01-01 Online:2009-01-20 Published:2009-01-20
Contact: TANG Changjie

摘要/Abstract

摘要： R-Tree及其变种的多维索引结构在数据的操作过程中通过对空间的分隔和不断调整将整个空间划分为大小不等的子空间以容纳足够的空间对象，这种方法能有效地实现多维空间对象的索引，但不能避免频繁的节点分裂与重组操作所造成的计算开销，也不能避免对叶子节点中的候选对象进行空间匹配所带来的计算开销。提出了一种能有效解决上述问题的索引结构：SHG-Tree。基于SHG-Tree的索引方法将多维空间划分为不同粒度的格子单元并将这些格子单元通过SHG-Tree按空间包含关系组织为层次树结构，同一层的格子互不相交且空间范围固定。空间对象通过文中提出的线性化方法转换为一系列不同粒度的互不相交的空间格子，进而将对象在其覆盖的格子中注册以实现空间对象至SHG-Tree的映射。查询操作只需将查询条件映射为相应的格子并取出这些格子中的对象作为查询结果。这种索引结构能有效减少节点的分裂和组合带来的计算开销，也解决了传统R-Tree索引中对于叶子节点中的候选对象进行区域匹配的计算开销。基于SHG-Tree的索引结构支持包括相交查询、区域查询、包含查询、top-N查询、k-NN查询等常用的多维查询，实验表明SHG-Tree能在毫秒级实现各种空间查询。

关键词: 空间索引, 空间超立方格子树, 对象线性化

Abstract: To improve query efficiency of multidimensional spatial database， a new index structure named spatial hypercube grid tree （SHG-Tree） is proposed. By decreasing the occurrence of node split and recombination during insert/delete operations， and avoiding range comparison between query range and candidate entities during query operations， SHG-Tree based index method can efficiently support the common operations over spatial database containing objects with dynamic region. The main contributions include：（1） Proposes two type of SHG-Tree for n-dimensional space. The hierarchical structure of SHG-Tree reflects the region overlapping relationship of hypercube grid units with different granularity. （2） Proposes three linearization strategies to present the bounding rectangle of spatial object as a union of variant granularity hypercube grids. （3） Gives the realization of different spatial query operations based on SHG-Tree. （4） Demonstrates the efficiency of SHG-Tree by extensive experiments. Experiments result shows query operation can be limited into ten milliseconds to ensure the real-time of query.

Key words: spatial index, spatial hypercube grid tree （SHG-Tree）, linearization of spatial object

刘胤田1,2 ,刘应明1 ,徐开阔3 ,曾涛4 ,唐常杰3+ . 多维空间索引结构SHG-Tree[J]. 计算机科学与探索, 2009, 3(1): 68-90.

LIU Yintian^1,2, LIU Yingming¹, XU Kaikuo³, ZENG Tao⁴, TANG Changjie³⁺. SHG-Tree： An Efficient Index Structure of Spatial Database[J]. Journal of Frontiers of Computer Science and Technology, 2009, 3(1): 68-90.

[1]	申金鑫，吴烨，陈荦，景宁. 面向空间在线分析的并行近似聚集查询[J]. 计算机科学与探索, 2018, 12(10): 1559-1570.
[2]	胡昱璞，牛保宁. 动态确定K值聚类算法的R-树空间索引构建[J]. 计算机科学与探索, 2016, 10(2): 173-181.
[3]	吴烨, 熊伟, 蔡蕾, 景宁. 面向多核处理器的空间数据库索引性能分析[J]. 计算机科学与探索, 2011, 5(8): 707-718.
[4]	李佳佳1 , 王波涛1+ , 陈东1 , 喜连川优2 , 王国仁1 . 分组移动对象的区域偏离监视算法*[J]. 计算机科学与探索, 2010, 4(9): 803-811.
[5]	王波涛1+ ，陈贺1 ，马俊1 ，喜连川优2 ，王国仁1 . 利用覆盖区域设计与实现移动对象索引[J]. 计算机科学与探索, 2010, 4(1): 64-72.

多维空间索引结构SHG-Tree

SHG-Tree： An Efficient Index Structure of Spatial Database

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics