Privacy-Preserving Record Linkage with Spark论文总结

Privacy-Preserving Record Linkage with Spark论文总结

• Abstract

• I. INTRODUCTION

• • PPRL
  • • A. Applications of PPRL
    • B. The PPRL process
    • C. PPRL and Big Data

• II. RELATED WORK

• • A. Secure multi-party computation
  • B. LSHDB

• III. ENCODING

• • A. Field-level Bloom filters
  • B. Record-level Bloom filters

• IV. MATCHING

• • A. Locality-sensitive hashing
  • B. Hamming LSH

• V. IMPLEMENTATION

• • A. Single-node evaluation
  • B. Cluster deployment evaluation

• VI. DISCUSSION

• VII. FUTURE WORK

• VIII. CONCLUSIONS

Abstract

Index Terms—linkage, PPRL, privacy, scalability, Spark

• 利用隐私保护记录链接 (PPRL) 来防止敏感信息不必要地暴露给其他组织
• 在处理数百万条记录时，基于 Spark 的 PPRL 解决方案优于其他解决方案；可以扩展到几十个节点；并且在取得的结果方面与常规记录链接实施相当。
• 随着正在收集和分析的个人数据的增加，需要能够处理海量数据库的可扩展 PPRL。
• Apache Spark 作为扩展 PPRL 的一个选项
• 可扩展的 PPRL 实施不仅很有价值，而且基于 Spark 的实施也可以普遍部署
  

I. INTRODUCTION

PPRL

A. Applications of PPRL

犯罪和欺诈检测、政府服务和医疗保健领域

隐私保护相似性搜索privacy-preserving similarity search (PPSS)
实体不再与单个其他实体匹配，而是与多个相似实体匹配。

B. The PPRL process

two party protocol 、 three-party protocol
两方协议被认为更安全，但比三方协议在计算上更加密集和复杂。

六个连续的过程：参数对齐、数据预处理、索引、比较、分类和评估

1. Parameter alignment: encoded、use the same parameters  

对记录进行编码，使其他参与者无法恢复字段的原始值。
使用相同的参数，以便对编码记录进行有意义的比较

2. Data pre-processing: clean and format these QIDs in a uniform way （那是不是说每个组织要提前确定好统一的参数，并且这个参数还不能让第三方知道，然后第三方不跟任何一个组织沟通其他的信息，这样组织也就无法得知其他组织的信息）

3. Indexing: only comparing 比较次数可能是 n^p（最坏情况）  

grouped records

4. Comparison:

5. Classification:知道两条记录（不）相似，就可以进行分类：匹配或不匹配  

与经常应用机器学习的常规记录链接相比， 尚未彻底探索除简单阈值函数之外的其他决策模型 。

6. Evaluation: accuracy, precision, recall

C. PPRL and Big Data

II. RELATED WORK

A. Secure multi-party computation

• secure multi-party-computation (SMC)
• 两个或多个参与方在没有中间人的情况下共同解决计算问题 。各方的输入不会透露给其他方。之后每一方都会收到打算解决的计算输出。
• 缺点：计算开销
  

B. LSHDB

使用 LSHDB 与我们的 Spark 实现进行比较

batch processing: 批量处理

III. ENCODING

• 采用了布隆过滤器数据结构
• 直接使用加密散列函数进行编码相比，Bloom 过滤器编码的优势在于输入的微小差异不会产生完全不同的输出。
• 也可用于值的近似匹配
• field-level
  Bloom filters (FBF)字段级 、 record-level Bloom filters (RBF)记录级

A. Field-level Bloom filters

• 首先创建长度为 mFBF 的位向量 vFBF。
• 使用空格填充的字段 f 被标记为集合 T
• 使用大小为 2 的 n-gram 作为标记。
• 使用 k 个独立的散列函数对每个令牌进行散列

FBF 中大约 50% 的位设置为 1（即均匀分布）。这最大化了熵，从而提高了安全性
动态 FBF 大小调整:
g，表示 T 中特定字段（跨所有记录）的平均令牌数量。
p， 代表生成的 FBF 中的位保持为 0 的概率。p=0.5

数字数据的编码：
整型值：

• 不使用 n-gram 作为标记，而是使用相邻数字作为标记来构造 T。
• 整数值 x，在这种情况下，标记是 [x - b, x + b] 范围内的数字，区间为 bintv
• 较低的 b 值 (1 ≤ b ≤ 4) 会提高准确性，使用更高的 b 值可以实现更大程度的隐私保护。

浮点值：
问题：令牌是 {4.5, 5.0, 5.5, 6.0, 6.5}。值 5.6 非常接近 5.5，但是对应的令牌集 {4.6, 5.1, 5.6, 6.1, 6.6}
方法：

B. Record-level Bloom filters

• 将记录的 FBF 组合成单个 RBF。
• 由于两个记录的相似性可以通过单个 RBF 比较来确定，而不是每个 FBF 的成对比较。
• 使推断原始字段值变得更加困难，从而提高了隐私保护

构造过程： 有点迷

• 创建长度为 mRBF 的位向量 vRBF，FBF 的样本大小是其权重 wi 乘以 mRBF。
• 接下来，随机抽取一个样本，进行替换
• vRBF 中的位被随机打乱

IV. MATCHING

编码后，链接单元只剩下一组 RBF 来操作。

RBF 具有可以计算它们之间的相对距离的特性。此属性允许将 RBF 的集合视为度量空间

RBF 本质上是位向量，因此适用的度量空间可以定义为 H^n =({0, 1}^n,d)，其中 n = mRBF。

这对应于一个汉明空间，因此使用汉明距离作为距离函数 d 是有意义的。

在汉明空间内寻找匹配可以推广到 k 最近邻 (k-NN) 问题，其中 k = 1 用于 PPRL 或 k ≥ 2 用于相似性搜索

A. Locality-sensitive hashing

使用 PPRL，一种索引方法可以有效地对相似的 RBF 进行分组

仅对同一组中的 RBF 进行成对比较，可以大大减少必须执行的比较总量。这称为阻塞 blocking

阻塞基于阻塞键创建项目组或块。

要将阻塞应用于 RBF，必须基于 RBF 创建阻塞密钥，这样类似的 RBF 将具有相同的阻塞密钥，因此最终在同一个块block中。

为了创建这些阻塞密钥，我们使用局部敏感哈希（LSH）

与旨在防止冲突的密码散列函数相比，LSH 函数是散列函数，旨在在基于 d 的度量空间内非常接近的输入的情况下发生冲突。此属性使 LSH 函数的输出适合用作阻塞键。

与成对线性搜索pairwise linear search相比，它缩小了搜索范围，从而提高了可扩展性。

B. Hamming LSH

适用于汉明空间的 LSH 技术是 Hamming LSH (HLSH)

从 RBF 中采样 k 位以创建其阻塞密钥，基于矩阵乘法的实现，比基于迭代的实现快三倍。

迭代每个输入项： h2(x1)是不是错了？？

位采样也可以使用矩阵乘法来实现 k没有理解

V. IMPLEMENTATION

基于 Spark 的 PPRL 实现变体。一个使用resilient distributed dataset弹性分布式数据集 (RDD) API，另一个使用 Spark SQL

RDD API 是一个低级 API，它提供对执行操作的扩展控制。

Spark SQL 是一个更高级别的 API，它允许 Spark 使用 Catalyst 优化器 [2] 执行优化。

两个阶段。

在第一阶段，相关组织加载（并清理，如果需要）他们的记录并将它们编码为 RBF。
此外，对于每个 RBF，使用第 IV-B 节中描述的矩阵乘法方法生成一组 L HLSH 阻塞密钥。
然后，将输出存储在磁盘上，以便将其传输到链接单元 。
第一阶段对应于 PPRL 过程的第二步（数据预处理，I-B 部分）。

链接单元执行第二阶段。
这一阶段的步骤在很大程度上（逻辑上）在 RDD API 和 Spark SQL 实现之间是相同的，只是候选的生成（步骤七）有很大不同，并影响后续步骤的实现。
生成哈希表条目的步骤。

总体思路是以分布式方式构建 L 个哈希表

在第六步中，每个记录条目被复制到 L 个单独的（哈希表）条目中，每个条目都有一个与之关联的 HLSH 阻塞键。这种方法允许 Spark 独立处理条目，从而并行处理哈希表。

7 的目标是找到具有至少一个具有匹配索引的 HLSH 阻塞键的记录对，即找到 L 个哈希表中的冲突。
只有这些记录将被考虑用于未来的步骤，因此称为候选记录。
RDD API 实现通过对 HLSH 阻塞键执行 cogroup 来生成候选记录对。
Spark SQL 实现根据哈希表条目以不同的方式生成候选记录对，它基于 HLSH 阻塞键执行 INNER JOIN。这导致与 RDD API 实现相同的候选记录对，但它们没有按 HLSH 阻塞键分组，因此可以独立处理。

比较记录，即计算汉明距离，是使用优化的按位运算完成的。

分配分类是基于阈值函数完成的，其中阈值是一个参数。

存储记录使用 Parquet 格式完成，但可以替换为与 Spark 和 Hadoop (HDFS) 兼容的任何其他格式。

A. Single-node evaluation

由于 LSHDB 不支持集群部署，因此使用单节点设置
使用了基准数据集：北卡罗来纳州投票登记 (NCVR)

LSHDB 对于多达一百万条记录的速度比这两种 Spark 变体都要快。
可以通过 Spark 的开销来解释，即除了实际工作之外，还执行作业调度和其他与集群相关的任务，即使在单节点设置上也是如此。
RDD API 实现的性能都比 Spark SQL 实现和 LSHDB 差。
随着数据库大小的增加，Spark 似乎更好地优化了 Spark SQL 的实现
Spark SQL 实现成为处理数百万条记录的最快选择，而 LSHDB 成为处理数百万条记录的数据库的最快选择。

分数都相当（表 I）。除了召回

虽然 Spark SQL 的实现，与 LSHDB 相比，随着更多记录的添加而变得更快，但它带来了一个折衷，即找到更少的真实匹配记录，即有更多的假阴性。

B. Cluster deployment evaluation

集群部署评估
为了衡量创建的 Spark 实现变体的可扩展性，它们在部署到 Hadoop 集群后进行了基准测试。
已使用与之前相同的生成的两个数据库配置 (NCVR)。考虑了不同的集群大小

我们可以得出结论，对于 RDD 实现，将节点增加一倍（最多 40 个节点）有利于减少运行时间，但除此之外，成本效益实际上变得几乎为零。

VI. DISCUSSION

HLSH 方法的一个缺点是，为每条记录单独生成阻塞键，而不考虑数据库中的任何其他记录，即 HLSH 是数据无意识的 data-oblivious

对于 HLSH，只有具有完全相同的阻塞键的记录才被视为候选记录对。例如，如果对于某个哈希表，两条真正匹配的记录生成的 HLSH 阻塞键仅相差一位，则这两条记录最终不会成为基于该哈希表的候选记录对。

因此，必须为每条记录提前生成多个 HLSH 阻塞密钥，以增加与真正匹配记录发生冲突的概率。

Spark 并不适用于单节点部署，并且在部署在集群上时效果会更好。

VII. FUTURE WORK

在这项工作中只使用了 Spark。然而，Hadoop 生态系统由几个其他框架组成。例如，另一种选择是 Apache Flink

Flink 提供了与 Spark 类似的计算抽象，但主要侧重于流处理。这适合具有实时入站记录流的用例，例如在边境安全应用程序中

大多数所需的计算可以定义为向量或矩阵运算。通过利用 GPU 的并行特性，可以更有效地执行此类操作。通过在 GPU 而不是 CPU 上执行所需的加密散列，GPU 也可用于加速 RBF 的创建。

VIII. CONCLUSIONS

在处理数百万条记录时，就总运行时间而言，基于 Spark 的 HLSH 实现 (Spark SQL) 能够胜过 LSHDB。
然而，这是以找到更少的真正匹配为代价的。就实现的准确性而言，两个考虑的 Spark 实现的性能都比 LSHDB 略差。但是，基于 Spark 的实现可以部署在集群上，从而进一步减少运行时间。