基于最大间隙空间映射的高维数据索引技术

被引：9

作者：

王国仁

黄健美

王斌

韩东红

乔百友

于戈

机构：

[1] 东北大学信息科学与工程学院

来源：

软件学报 | 2007年 / 06期

关键词：

高维索引; 查询精炼; 假活动子空间;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

在基于高维索引技术的相似性查询处理中,通常通过过滤那些不包含任何查询结果的非活动子空间来不断缩减搜索空间.但是在活动子空间中,有些可能根本就不包含任何查询结果,这样的活动子空间被称为假活动子空间.显然,查询处理性能会随着假活动子空间访问次数的增加而下降.这一问题在高维数据情况下将会变得更加严重,实验显示出随着维数的增加,假活动子空间的访问次数也会增加.为了解决这一问题,提出了一种空间映射方法来减少这种不必要的访问.对于一个给定的查询,可以通过在映射空间内进一步精炼该查询来过滤假活动子空间.为了提高映射空间内查询精炼的处理效率,提出了一个最大间隙空间映射策略——MaxGapMapping.基于这种映射方法,设计并实现了一种新的索引结构——MS-tree,给出了索引的构建算法和范围查询处理算法.最后对MS-tree及其他索引结构的性能进行了详细的比较和分析.

引用

页码：1419 / 1428

页数：10

共 6 条

[1] 批量构建M+-tree [J].

周项敏 ;

王国仁 ;

常立 ;

范丹 .

小型微型计算机系统, 2006, (02) :295-299

[2] VA-Trie:一种用于近似k近邻查询的高维索引结构 [J].

董道国 ;

刘振中 ;

薛向阳 .

计算机研究与发展, 2005, (12) :2213-2218

[3] 一种支持快速相似检索的多维索引结构 [J].

冯玉才 ;

曹奎 ;

曹忠升 .

软件学报, 2002, (08) :1678-1685

[4] Managing very large document collections using semantics [J].

Wang, GR ;

Lu, HJ ;

Yu, G ;

Bao, YB .

JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2003, 18 (03) :403-406

[5]

Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances[J] . Ada Wai-chee Fu,Polly Mei-shuen Chan,Yin-Ling Cheung,Yiu Sang Moon.The VLDB Journal . 2000 (2)

[6]

The TV-tree: An index structure for high-dimensional data[J] . King-Ip Lin,H. V. Jagadish,Christos Faloutsos.The VLDB Journal . 1994 (4)

← 1 →