收稿日期:20131018;修回日期:20131210 基金项目:浙江省公益性技术应用研究计划资助项目(2011C21076)
作者简介:徐媛媛(1989),女,安徽合肥人,硕士,主要研究方向为数据流处理(xuyuanyuan1109@163.com);陈华辉(1964),男,教授,博士,
主要研究方向为数据库、数据挖掘、数据流处理.
基于 MapReduce的增量式数据集的相似性连接
徐媛媛,陈华辉
(宁波大学 信息科学与工程学院,浙江 宁波 315211)
摘 要:相似性连接,即利用相似函数度量数据之间的相似程度,满足条件后进行连接操作。MapReduce框架
下已存在很多相似性连接算法,但仍然存在一些不足,如大量的索引加大时间、空间的开销;现有算法不能有效
地完成增量式数据集的相似性连接等。针对海量增量式数据集进行了研究,采用抽样技术得到有效中枢,形成
更为合理的分区,建立分区索引和分配原则,完成新增数据的相似性连接操作。实验证明,该算法能够有效地解
决海量增量式数据集的相似性连接问题,验证了分区索引的建立,可以提高新增数据的相似性连接操作的效率。
关键词:海量增量式数据集;划分;相似性连接;MapReduce
中图分类号:TP311.1 文献标志码:A 文章编号:10013695(2014)11336906
doi:10.3969/j.issn.10013695.2014.11.039
MapReducebasedsimilarityjoinforincrementaldataset
XUYuanyuan,CHENHuahui
(CollegeofInformationScience&Engineering,NingboUniversity,NingboZhejiang315211,China)
Abstract:Similarityjoinwasnamelythatusingsimilarfunctiontomeasurethesimilaritylevelofthedataset,andthendoing
thejoinaftermeetingthecondition.Manyeffectivesimilarityjoinalgorithmshadbeeninmapreduce
,buttherewerestillsome
insufficiency,suchasalotofindexesincreasestheoverheadoftimeandspace;theexistingalgorithmcouldn’tdealwiththe
similaritycomputationoftheincrementaldataseteffectively,andsoon.Formassiveincrementaldataset,thispapermadeuse
ofsamplingtogetthevalidpivots,whichestablishedpartitions’indexesanddistributionprinciple,thenfinishedthesimilarity
joinoperationofadditionaldata.Theexperimentsprovethatthealgorithmcansolvetheproblemofthesimilarityjoinofthein
crementaldataseteffectively,andverifythatthroughcreatingpartitions’indexes,itcanimprovetheefficiencyofthesimilari
tyjoinoperationofadditionaldata.
Keywords:massiveincrementaldataset;partition;similarityjoin;MapReduce
'
引言
给定数据集 R和 S、阈值
ε
(常数)、相似度函数 sim,若 sim(r,
s)不超出给定阈值
ε
(其中数据 r
∈
R,s
∈
S),那么判定(r,s)是相
似对。所谓相似性连接就是找到 R和 S中所有这样的相似对。
针对不同的数据类型和应用场景,可选用不同的相似度函数。
例 1 对集合数据 S
1
={A,B,C,D,E},S
2
={F,B,C,D,
E},S
1
和 S
2
的 Jaccard系数
|S
1
∩
S
2
|
|S
1
∪
S
2
|
=
4
6
=0.67,余弦系数
|S
1
∩
S
2
|
|S
1
槡
| |S
2
槡
|
=
4
槡槡
55
=0.8。给定不同的相似度函数和阈值,
就会有不同的相似对判定结果。若给定阈值
ε
=0.75,当相似
度大于 0.75时为相似对,那么通过 Jaccard系数进行判断,S
1
和 S
2
不能成为相似对,但通过余弦系数进行判断,则它们是相
似对。
例 2 有向量数据 x=(0.78,0.4,0.01),y=(0.77,0.42,
0. 02 ), 此 时 x 和 y 的 欧 氏 距 离
(0.78-0.77)
2
+(0.4-0.42)
2
+(0.01-0.02)
槡
2
=0.025,x
和 y的曼哈顿距离 |0.78-0.77|+|0.40-0.42|+|0.01-
0.02|=0.04,若给定阈值
ε
=0.03,当距离小于 0.03为相似
对,那么欧氏距离下
x和 y是相似对,而曼哈顿距离下 x和 y
不是相似对。
相似性连接,作为一种有效的数据处理和分析的操作,近
几年被学术界和工业界所关注,广泛用于数据仓库的数据清
理
[1]
、网页搜索中的重复和近重复网页检测
[2]
、电子商务系统
中的协同过滤
[3]
等应用中。
对相似性连接算法的研究目前已有很多,根据针对的数据
集类型的不同,可分为集合数据相似性连接、向量数据相似性
连接。面向集合数据相似性连接的算法主要有
SSJoin
[1]
、All
Pairs
[4]
、PPJoin及 PPJoin+ +
[2]
、EdJoin
[5]
、TrieJoin
[6]
、B+
tree
[7]
、vernica
[8]
、VSMARTJoin
[9]
等,其中针对字符串数据的
研究较为广泛,有基于编辑距离
[5]
、倒排索引
[1,2,4]
、签名
[10,11]
等的字符串连接。面向向量数据相似性连接主要有 Quick
join
[12]
、fullinvertedlist
[13]
、prefixfiltering
[14]
、VSMARTJoin、
bucketfiltering
[15]
、MRDSJ
[16]
等。通常将文本转换成向量数
据,再进行相应的相似性操作。
随着各类应用中数据规模越来越大,如何在 Hadoop等分布
式环境中对海量的数据进行相似性连接处理也已引起了研究者
的关注。文献[17]提出了一种 MapReduce框架下的相似性连
接算法
MRSimJoin。MRSimJoin对同一数据集进行相似性连接,
即自连接。自连接是一种应用相当普遍的相似性连接操作。
第 31卷第 11期
2014年 11月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.31No.11
Nov.2014