面向大数据的实体解析方法及关键技术研究

Entity resolution is the basic operation of data quality management, and the key step to find the value of data. The traditional research of entity resolution methods is focused on batch data processing and mainly aims at improving the accuracy of similarity matching algorithms. By analyzing the new requirements brought by big data, we find that parallel data processing with MapReduce using multi-pass blocking method can deal with this challenge. However, there are still several fundamental issues to be investigated, including providing support for incremental processing in the non-state environment, avoiding redundant pairs led by the multi-pass blocking method, optimizing pairs and detecting conflict based on the transitive similarity, and reducing the impact of data skew for load balancing. This project is proposed to find solutions to these issues. With our research, the signature-based entity resolution method with multi-pass blocking technology and the parallel computing model with the support of batch processing and incremental processing provide the theoretical and practical guidance for online record joining and duplicate object detection. They also show a new idea for online processing of streaming data with MapReduce model.

实体解析是数据质量管理的基本操作，也是数据价值发现的关键步骤。传统的实体解析方法研究只专注于数据的批量处理方式，其评价标准主要局限于相似度匹配算法的精度。通过分析大数据对实体解析提出的新要求，我们发现MapReduce并行计算环境下多路分块方法能够较好地应对此挑战，并抽象出几个尚待深入研究的重要问题，具体包括：1)在无状态编程环境中为增量式处理提供支持；2)消除多路分块方法带来的候选相似对冗余计算；3)基于相似度传递关系优化候选相似对并检测匹配冲突；4)通过动态划分策略减少数据倾斜对系统负载均衡的影响。本项目旨在对这一系列问题进行研究，探索增量式的基于标签的多路分块实体解析方法，以及批量和增量处理工作流融合的并行计算模型，为准确且高效的在线记录连接和重复对象检测提供理论和实践上的指导，为MapReduce模型支持流式数据在线处理提供新的思路。

实体解析是数据质量管理的基本操作，也是数据价值发现的关键步骤。通过分析大数据对实体解析提出的新要求，我们发现MapReduce并行计算环境下多路分块方法能够较好地应对此挑战，并抽象出几个尚待深入研究的重要问题，本项目旨在对这些问题进行研究，具体包括：.首先，提出一种基于多标签的实体解析方法multi-sig-er，在不影响解析精度的情况下采用两个策略减少冗余匹配次数，从而提高解析效率，实验结果表明该方法更加适合处理大规模数据集以及相似性计算比较复杂的实体解析数据。.其次，提出一种用于字符串相似性连接的并行处理框架，多核系统中的实现是基于多线程技术的Para-Join算法，集群系统中的实现是基于Spark平台的Pada-Join算法。实验证明两种算法都能在保证结果完整性的同时有效避免冗余计算，而且Pada-Join能适合于处理大规模数据集。.第三，提出一种用于字符串相似性连接的增量式处理框架，该增量模型能够避免历史字符串重复相似性计算带来的时间和空间代价，适合处理数据流。提出两个算法Inc-join和Inp-join，前者运行于单机，后者运行于Spark平台的集群环境。实验表明该框架能够显著提高流式数据的响应时间。.第四，研究虚拟机的放置问题。通过考虑虚拟机的放置以及物理节点拓扑结构的影响，优化云环境中虚拟集群的网络延迟，定义节点之间的距离，用于衡量虚拟集群的亲密性，把距离最小化问题形式化为经典的最短距离问题，通过构建整数规划模型，提出相关的优化算法。.所有的实验数据集均来自于真实世界，为准确且高效的在线记录连接和重复对象检测提供理论和实践上的指导，为MapReduce模型支持流式数据在线处理提供新的思路。