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

作     者：王金宝 高宏 李建中 杨东华 WANG Jin-Bao;GAO Hong;LI Jian-Zhong;YANG Dong-Hua

作者机构：哈尔滨工业大学计算机科学与技术学院哈尔滨150001 哈尔滨工业大学基础与交叉科学研究院高性能计算中心哈尔滨150001 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2011年第34卷第11期

页      面：2142-2154页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 0839[工学-网络空间安全] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家"九七三"重点基础研究发展规划项目基金(2012CB316200) 国家自然科学基金(60903016 61003046 60533110 60773063 61173022) 黑龙江省自然科学基金(F201031) 中国博士后科学基金(20110491064) 黑龙江省博士后基金(LBH-Z09140) 哈工大科研创新基金"中央高校基本科研业务费专项资金"(HIT.NSRIF.2010060) 哈工大优秀青年教师培养计划(HITQNJS2009.063)资助 

主　　题：字符串 相似性 索引 查询处理 连接处理 

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