多维空间索引结构SHG-Tree

• 作者: 刘应明 刘胤田 唐常杰 徐开阔 曾涛
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 空间索引 空间超立方格子树 对象线性化
• 年，卷（期）: 2009,（1）
• 所属期刊栏目: 综述·探索
• 页码范围: 68-90
• 页数: 23页
• 分类号: TP301
• 字数: 2871字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2009.01.007

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐常杰	四川大学计算机学院	164	2750	30.0	45.0
2	曾涛	天津师范大学计算机与信息工程学院	6	34	4.0	5.0
3	徐开阔	四川大学计算机学院	17	63	6.0	7.0
4	刘应明	四川大学数学学院	10	88	4.0	9.0
5	刘胤田	四川大学数学学院	13	64	4.0	7.0