MERLIN-AToolfor Multi-party Privacy-preserving Record Linkage论文总结

---

Abstract

在本文中，我们介绍了Merlin，一个在多方环境中演示各种PPRL方法的在线工具。
在这个演示中，我们展示了不同的私有多方阻塞和匹配技术； 并通过介绍各种PPRL方法的质量和性能度量来说明Merlin的可用性。
我们相信Merlin将帮助实践者和研究人员更好地理解PPRL过程的管道，比较不同的多方PPRL技术，并确定适合他们需要的最佳技术。
Keywords—Privacy, data matching, Bloom filters, scalability, online demo.
2015

---

I. INTRODUCTION

从多个数据库中识别涉及同一实体的匹配记录的过程称为记录链接、实体解析或数据匹配[1]。

由于数据库中缺乏唯一的实体标识符，记录链接过程通常需要使用准标识符[2]，如名字和姓氏、地址细节等来匹配记录。 然而，由于对隐私和保密的关切，很难使用这类QID，因为各组织一般不想与其他组织分享关于其实体的任何敏感信息。 在多个数据库中查找与同一实体相关的记录或一组QID具有大致相同值的记录，而不泄露关于这些记录的任何私人或敏感信息，这是一个被称为隐私保护记录链接(PPRL)[2]的研究领域。

为了提高链接质量，首先必须使用相同形式的数据清洗和标准化来处理要链接的数据库[1]。 一旦数据库所有者同意如何清理和标准化他们的数据库，这个预处理可以由每个数据库所有者独立进行。 在这个演示中，数据库的预处理不包括在内，相反，我们假设所有各方都以相同的格式提供他们的数据。

PPRL流程由图所示的几个步骤组成
在第一步（参数设置和数据掩蔽）中，各方商定用于链接的参数和掩蔽（编码）函数。
在第二步（私有块）中，通过使用私有块函数[3]来减少搜索空间，该函数删除尽可能多的对应于不匹配的记录集。
这导致在第三步（私有匹配和分类）中要安全地比较和分类的候选记录集数量较少[2]。
最后，作为第四步（评估），从复杂度（或可扩展性）、链接质量和隐私性等方面评估链接的性能。

没有软件解决方案可以在多方（两个以上）环境中执行PPRL。

为此，我们介绍了Merlin（Multi-Party PrivacyProveing Record Linking)，
这是第一个基于Web的工具，它展示了在越来越多的参与方上执行PPRL的最先进技术。 MERLIN旨在帮助研究人员和实践者实践和比较适用于不同多方场景的不同PPRL技术。

考虑到PPRL中涉及的各个步骤，Merlin由明显分离的模块组成，每个模块执行PPRL过程中的一个特定步骤。 我们以分离类的形式实现了各种隐私保护、阻塞和匹配技术，这为部署提供了灵活性。

---

II. OVERALL ARCHITECTURE OF MERLIN

总体架构

Merlin是遵循瘦客户机服务器体系结构开发的，该体系结构允许用户通过Web界面访问PPRL功能。

然而，在多方场景中运行PPRL技术需要参与方之间的分布式操作和通信。 Merlin目前通过为每一方创建一个目录并将通信数据写入这些目录中的一个文件来模拟各方之间的通信来实现这一要求。
未来，我们计划在一个完全分布式的基础设施中实现Merlin。
在评估中，我们目前侧重于处理成本，而不检查通信成本和数据传播延迟。

A. MERLIN Interface

Merlin Web界面由五个制表器（标签）组成，其中第一个是主页标签，它欢迎用户进入演示并提供关于PPRL管道（如图1所示）、如何使用标签以及与在Merlin中实现的PPRL技术相关的出版物的信息。

第二个选项卡（参数设置和数据掩蔽），如图所示 2、允许用户在演示中设置要链接的当事人及其数据集的数量，以及数据掩蔽设置。

在本演示中，屏蔽功能目前仅限于Bloom Filter编码[5]，因为在Merlin中实现的所有多方PPRL技术都基于Bloom Filter编码方法。
图 2说明了在记录链接过程的分块和匹配步骤中QID选择不需要相同。

一旦根据在参数设置和数据掩蔽标签上提供的设置将原始记录转换为掩蔽记录，则在可以执行匹配和分类步骤之前将它们排列成块。
应用索引或分块[1]在多方方案中很重要，因为记录的成对比较随着参与方数量的增加呈指数增长[4]。 图3中显示的第三个选项卡（私有阻塞） ,为用户提供若干专用阻塞技术[3]、[4]的选择，以及特定于所选阻塞技术的参数设置。

然后在下一个选项卡（私有匹配和分类）上使用阻塞的数据集，如图所示 4. 此选项卡说明了在PPRL处理的匹配和分类步骤中，如何根据计算出的相似性对记录集进行分类。 用户被赋予选择私有匹配和分类技术[6]，[7]的能力，以将候选记录集比较和分类为匹配和不匹配。

在图显示的最后一个选项卡（评估）上 5、用户可以查看所进行的多方PPRL在效率、效果和隐私方面的表现[8]。

B. Implementation

我们使用HTML和PHP进行Web界面开发，使用JavaSript对象表示法(JSON)进行浏览器和Merlin服务器之间的数据交换。

C. Implemented Algorithms and Evaluation measures

实施的算法和评价措施

• 1. Private blocking techniques:
     Merlin包含几种可扩展的多方PPRL阻塞技术。
     第一种是基于树的多方私有阻塞技术[3]，它使用Bloom过滤器来掩蔽记录。 块被生成为树中的叶节点，可以使用私有匹配和分类技术进行比较。
     其次，提出了两种基于聚类的私有分块技术[4]，它们分别是基于标准树冠聚类算法[10]和基于层次树冠聚类算法[4]。
• 2. Private matching and classification techniques:
     [6]是在Merlin中实现的一种私有的精确匹配和分类技术，可以用作比较精确和近似匹配技术的基线。
     它结合了Bloom过滤器、安全求和[3]和DICE系数[1]相似度计算的使用，旨在识别不同数据库保存的所有相似记录。
• 3. Evaluation measures:
     从质量、效率和私密性三个方面对私有阻塞和私有匹配分类技术的性能进行了评价。

---

III. DEMO SCENARIOS

可以通过URL : MRELIN访问Merlin。

IV. CONCLUSION AND FUTURE WORKS

在本文中，我们介绍了Merlin，这是一个基于Web的、易于配置的工具，使用户能够熟悉不同的多方PPRL技术。 参数配置的灵活性有助于用户评估PPRL技术，并为他们的记录链接场景选择最合适的方法。 我们相信Merlin将是一个有价值的工具来实践不同的多方PPRL算法的效率，有效性和隐私。

作为未来的工作，我们计划实现其他多方PPRL分块和匹配技术，以及文献中提出的数据掩蔽（编码）功能。 允许用户上传他们自己的数据集在Merlin中使用是我们打算在Merlin的持续发展计划中包括的另一个扩展。 为了提高系统的性能，我们还引入了并行化。