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

第34卷第11期 计 算 机 学 报 V01．34No．II 201 1月 CHINESE Nov．2011 1年1 JOURNALOFCOMPUTERS ●l● RM树种支持字符串相似性操作的索引 王金宝” 高 宏n 李建中” 杨东华2’ 1’(哈尔滨工业大学计算机科学与技术学院哈尔滨150001) 2’(哈尔滨工业大学基础与交叉科学研究院高性能计算中心哈尔滨150001) 摘 要 字符串相似性操作在很多领域中被广泛应用，如数据清洁、信息集成等．现有研究工作主要为基于q-Gram 和倒排索引的内存方法。在处理大量数据时具有以下缺点：内存消耗大、更新效率低、支持操作类型有限．现有的外 存索引∥树无法将相似的字符串聚类。在查询处理过程中导致了较大的I／0代价．该文设计了支持多种字符串相 似性操作的RM树索引，消除了现有内存方法的缺点，并通过字符串聚类的方法提高了相似性操作的效率．该文通 过大量实验结果证明了RM树的有效性． 关键词 字符串}相似性；索引；查询处理；连接处理 中图法分类号TP311DOI号：10．3724／SP．J．1016．2011．02142 RM—Tree·AnIndex StringSimilarityOperations Supporting WANG GAO YANG Jin-Ba01’ Hon91’LIJian-Zhon91’ Dong—Hua2’ ”(School Scienceand Institute 150001) of Technology，Harbin Computer ofTechnology，Harbin 2’(Center Fundamentaland forHighPerformanceComputing．Academyof Interdisciplinary， HarbinInstitute 150001) ofTechnology，Harbin Abstract iswell invariousfieldssuchasdata Stringsimilarityprocessingadopted cleaning．in— the formation checkandbioinformatics．Withofinformation， integration，spelling rapidgrowth datasetsbecomesa basic overmassive solutions strings significantoperation．Existing processing sufferfromthe b