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

• 作者: 曹海 陈懿诚 骆吉洲
• 来源期刊: 智能计算机与应用
• 学科: 工学
• 关键词: 字符串相似连接 编辑距离 外存算法 数据划分
• 年，卷（期）: 2012,（5）
• 页码范围: 31-34,38
• 分类号: TP391.41
• 字数: 5205字
• 语种: 中文
• DOI: 10.3969/j.issn.2095-2163.2012.05.009

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	骆吉洲	哈尔滨工业大学计算机科学与技术学院	24	310	8.0	17.0
2	陈懿诚	哈尔滨工业大学计算机科学与技术学院	2	7	2.0	2.0
3	曹海	哈尔滨工业大学计算机科学与技术学院	1	4	1.0	1.0