%0 Journal Article
%T BMGSJoin:一种基于MapReduce的图相似度连接算法*
%A 陈一帆
%A 赵翔
%A 何培俊
%A 张维明
%A 唐九阳
%J 模式识别与人工智能
%P 472-480
%D 2015
%R 10.16451/j.cnki.issn1003-6059.201505011
%X 图相似度连接在数据挖掘领域应用广泛，尤其是在数据预处理阶段，可用于数据清理、近复本检测等，其研究具有十分重要的意义.针对基于编辑距离约束的图相似度连接问题进行研究，返回两个图集合中所有编辑距离不超过给定阈值的图对.基于分布式编程框架MapReduce，设计采用“过滤-验证”框架的MGSJoin算法，利用基于路径的q-gram签名实现非解候选对的过滤，计数过滤.鉴于该算法键值对数量庞大的潜在问题，引入BloomFilter技术对算法进行改进并设计BMGSJoin算法.实验结果表明，提出的两种图相似度连接算法能较大地改善现有算法的效率和可扩展性，并能较好地应对当前大数据挖掘分析的需求.
%K 图相似度连接
%K MapReduce
%K 布隆过滤器
%U http://manu12.magtech.com.cn/Jweb_prai/CN/abstract/abstract10374.shtml