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

作者：王金宝; 高宏; 李建中; 杨东华

来源：计算机学报, 2011, (11): 2142-2154.

• 字符串
• 相似性
• 索引
• 查询处理
• 连接处理 string
• similarity
• index
• query processing
• join processing

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

• 单位
  哈尔滨工业大学