一种基于数据划分的字符串相似连接外存算法

A Data-Partition based Disk Algorithm for String Similarity Join

字符串相似连接操作具有广泛应用,因而将着重研究基于编辑距离的字符串相似连接。而现有的字符串相似连接算法大多为内存算法。实际应用中的数据集越来越大,有必要针对超大规模数据集研制字符串相似性连接外存算法。利用组合频率向量划分数据集,并提出了基于编辑距离的字符串相似性连接外存算法框架,证明了磁盘调度问题的难度并提出了不同的启发式磁盘调度方法。此外,还提出了基于该外存算法框架实现字符串相似性连接增量式计算的方法。实验结果表明,数据划分方法可以有效地过滤不相关的数据子集;磁盘调度算法能够有效减少磁盘IO次数;外存算法是高效的;增量式计算方法能够高效地处理数据更新。

String similarity join has a variety of applications. This paper focuses on the study of disk algorithms for edit string similarity join. The existing algorithms for this problem are all memory algorithms. It is necessary to study the disk algorithms, since the sizes of nowadays datasets are becoming bigger and bigger. The paper proposes to partition dataset into small chunks via combined frequency vec- tors, and implements a disk-algorithm framework. The disk scheduling problem is proved to be NP-complete, and several heuristics are pro- posed to solve this problem. The incremental computation, via the proposed disk algorithm framework, is also discussed. Experiments verify the key idea that similarity join based on partition can prune large amount of data subset pairs and the number of IO is reduced obviously and efficiently, which lay the foundation for future disk algorithms.