Top-k相似连接算法性能优化

发布时间：2017-09-17 20:52

  本文关键词：Top-k相似连接算法性能优化

  更多相关文章： Top-k相似连接 事件驱动框架 Token批处理 哈希查找优化

【摘要】：相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用.现有相似连接算法有两种类型:基于相似度阈值的相似连接和Top-k相似连接.Top-k连接算法非常适合于相似度阈值未知的应用场景,目前最为有效的Top-k相似连接算法是Xiao等人提出的Topk-join.为了解决Topk-join中存在的性能问题,提出了一种Top-k相似连接算法Opt-join,该算法将Token批处理技术集成在现有的事件驱动框架中,以降低前缀事件的处理代价;通过置换哈希查找与过滤操作的执行位置来降低哈希查找代价,并理论证明了该置换的正确性.实验结果表明:与Topk-join算法相比,Opt-join取得了1.28倍~3.09倍的性能提升.实验数据还显示:随着数据长度的增加或k值的增长,Opt-join的性能优势有不断增加的趋势.
【作者单位】： 东华大学计算机科学与技术学院;
【关键词】： Top-k相似连接 事件驱动框架 Token批处理 哈希查找优化
【基金】：国家自然科学基金(61370205) 上海市自然科学基金(13ZR1400800) 中央高校基本科研业务费专项资金~~
【分类号】：TP301.6
【正文快照】： cn/1000-9825/5012.htm英文引用格式:Wang HY,Yang LH,Liu XQ.Optimizing top-k similarity join algorithm.Ruan Jian Xue Bao/Journal of Software,2016,27(12):3051?3066(in Chinese).http://www.jos.org.cn/1000-9825/5012.htmOptimizing Top-k Similarity Join Algorithm

【相似文献】

中国期刊全文数据库 前10条

1 盛刚;温涛;郭权;印莹;;云计算中偏好top-k查询的正确性验证[J];吉林大学学报(工学版);2014年01期

2 张海杰;姜守旭;邹兆年;;不确定图上的高效top-k近邻查询处理算法[J];计算机学报;2011年10期

3 刘维弋;金远平;;一种基于动态修正值的分布数据流Top-K查询处理算法[J];计算机应用与软件;2009年01期

4 何盈捷;文继军;冯月利;王珊;;P2P环境下数据管理系统上的Top-k查询[J];计算机科学;2005年10期

5 甘亮;于莉莉;李润恒;贾焰;金鑫;;一种基于逆支配点集的数据流Top-k计算方法[J];计算机工程与科学;2012年06期

6 顾彦慧;赵斌;周俊生;曲维光;;Top-k相似短文本快速抽取算法[J];计算机科学与探索;2014年08期

7 张连宽;杨波;唐屹;;提高P2P下top-k搜索性能的研究[J];计算机应用研究;2009年01期

8 刘德喜;万常选;刘喜平;;不确定数据库中基于x-tuple的高效Top-k查询处理算法[J];计算机研究与发展;2010年08期

9 焦雷;;一种基于ZBDD结构的Top-k挖掘算法[J];现代计算机(专业版);2011年25期

10 兰超;张勇;邢春晓;;海量多版本文档的加权持久性top-k检索[J];计算机研究与发展;2013年S2期

中国重要会议论文全文数据库 前3条

1 佟星;王宏志;李建中;高宏;;基于树结构索引的带权值字符串的Top-k查询算法[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

2 张丽;贾焰;邹鹏;;一种数据流上的多Top-k查询资源共享技术研究[A];第八届全国信息隐藏与多媒体安全学术大会湖南省计算机学会第十一届学术年会论文集[C];2009年

3 刘德喜;万常选;刘喜平;;不确定数据库中基于x-tuple的高效Top-k查询处理算法[A];第26届中国数据库学术会议论文集（A辑）[C];2009年

中国硕士学位论文全文数据库 前4条

1 杨健;基于编辑距离字符串Top-k相似性搜索算法的研究[D];哈尔滨工业大学;2015年

2 刘玉静;针对K-匿名数据的top-k查询问题研究[D];东华大学;2014年

3 黎玲利;XML数据流上的TOP-K关键字查询处理[D];哈尔滨工业大学;2010年

4 卢鑫;云环境下海量不确定性数据的Top-k查询技术[D];宁波大学;2013年

，

本文编号：871281