RB树:一种支持空间近似关键字查询的外存索引

被引：8

作者：

王金宝 ^{[1
]}

高宏 ^{[1
]}

李建中 ^{[1
]}

杨东华 ^{[2
]}

机构：

[1] 哈尔滨工业大学计算机科学与技术学院

[2] 哈尔滨工业大学基础与交叉科学研究院高性能计算中心

来源：

计算机研究与发展 | 2012年 / 10期

关键词：

空间数据库; 关键字; 查询处理; 索引; 外存;

D O I：

暂无

中图分类号：

TP391.3 [检索机];

学科分类号：

摘要：

空间近似关键字查询包含一个空间条件和一组关键字相似性条件,这种查询在空间数据库中返回同时满足以下条件的对象:1)对象的位置信息满足查询中的空间条件;2)对于查询中的任何一个关键字,对象中至少包含一个关键字与其相似度大于给定阈值.随着当前数据的爆炸性增长,空间数据库无法完整地存放在内存中,因此空间数据库需要支持空间近似关键字查询的外存索引.目前,还没有在外存中支持精确的空间近似关键字查询的索引结构.设计了一种新型的外存索引RB树,在外存中支持精确的空间近似关键字查询.RB树支持的空间近似关键字查询包括多种空间条件,如范围查询、NN查询,同时支持多种关键字相似性度量,包括编辑距离、规范化编辑距离等.通过真实数据中的性能测试验证了RB树的效率.

引用

页码：2142 / 2152

页数：11