RM树:一种支持字符串相似性操作的索引

被引：6

作者：

王金宝 ^{[1
]}

高宏 ^{[1
]}

李建中 ^{[1
]}

杨东华 ^{[2
]}

机构：

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

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

来源：

计算机学报 | 2011年 / 34卷 / 11期

基金：

黑龙江省自然科学基金; 中国博士后科学基金;

关键词：

字符串; 相似性; 索引; 查询处理; 连接处理;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

字符串相似性操作在很多领域中被广泛应用,如数据清洁、信息集成等.现有研究工作主要为基于q-Gram和倒排索引的内存方法,在处理大量数据时具有以下缺点:内存消耗大、更新效率低、支持操作类型有限.现有的外存索引Bed树无法将相似的字符串聚类,在查询处理过程中导致了较大的I/O代价.该文设计了支持多种字符串相似性操作的RM树索引,消除了现有内存方法的缺点,并通过字符串聚类的方法提高了相似性操作的效率.该文通过大量实验结果证明了RM树的有效性.

引用

页码：2142 / 2154

页数：13