Differentially Private String Sanitization for Frequency-Based Mining Tasks
Differentially Private String Sanitization for Frequency-Based Mining Tasks
复制标题
DOI：
10.1109/icdm51629.2021.00014
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Huiping Chen;Changyu Dong;Liyue Fan;Grigorios Loukides;S. Pissis;L. Stougie
中科院分区：
文献类型：
--
作者：
Huiping Chen;Changyu Dong;Liyue Fan;Grigorios Loukides;S. Pissis;L. Stougie
字符串用于对基因组，自然语言和Web活动数据进行建模，因此经常被广泛共享。但是，字符串数据共享引起了隐私问题，这是因为对字符串长度为k的知识及其频率（多重性）的知识可能足以唯一地重建字符串；从中推断此类子字符串可能会泄漏机密信息。因此，我们介绍了通过应用差异隐私（DP）来保护单个字符串S的长度K子字符串的问题，同时最大程度地利用数据实用程序来实现基于频率的挖掘任务。我们的理论和经验证据表明，经典的DP机制不适合解决该问题。 In response, we employ the order-k de Bruijn graph G of S and propose a sampling-based mechanism for enforcing DP on G. We consider the task of enforcing DP on G using our mechanism while preserving the normalized edge multiplicities in G. We define an optimization problem on integer edge weights that is central to this task and develop an algorithm based on dynamic programming to solve it exactly.我们还考虑了带有实际边缘权重的两个变体。通过放松整数边缘权重的限制，我们能够为这些变体开发线性时间精确算法，我们将其用作有效启发式的踏脚石。使用现实世界大规模字符串（按数十亿个字母的顺序）进行了广泛的实验评估表明，我们的启发式方法是有效的，并且产生了近乎最佳的解决方案，可为基于频率的采矿任务保留数据实用性。
Strings are used to model genomic, natural language, and web activity data, and are thus often shared broadly. However, string data sharing has raised privacy concerns stemming from the fact that knowledge of length-k substrings of a string and their frequencies (multiplicities) may be sufficient to uniquely reconstruct the string; and from that the inference of such substrings may leak confidential information. We thus introduce the problem of protecting length-k substrings of a single string S by applying Differential Privacy (DP) while maximizing data utility for frequency-based mining tasks. Our theoretical and empirical evidence suggests that classic DP mechanisms are not suitable to address the problem. In response, we employ the order-k de Bruijn graph G of S and propose a sampling-based mechanism for enforcing DP on G. We consider the task of enforcing DP on G using our mechanism while preserving the normalized edge multiplicities in G. We define an optimization problem on integer edge weights that is central to this task and develop an algorithm based on dynamic programming to solve it exactly. We also consider two variants of this problem with real edge weights. By relaxing the constraint of integer edge weights, we are able to develop linear-time exact algorithms for these variants, which we use as stepping stones towards effective heuristics. An extensive experimental evaluation using real-world large-scale strings (in the order of billions of letters) shows that our heuristics are efficient and produce near-optimal solutions which preserve data utility for frequency-based mining tasks.