How can we explore the unknown properties of high-dimensional sensitive relational data while preserving privacy? We study how to construct an explorable privacy-preserving materialized view under differential privacy. No existing state-of-the-art methods simultaneously satisfy the following essential properties in data exploration: workload independence, analytical reliability (i.e., providing error bound for each search query), applicability to high-dimensional data, and space efficiency. To solve the above issues, we propose HDPView, which creates a differentially private materialized view by well-designed recursive bisected partitioning on an original data cube, i.e., count tensor. Our method searches for block partitioning to minimize the error for the counting query, in addition to randomizing the convergence, by choosing the effective cutting points in a differentially private way, resulting in a less noisy and compact view. Furthermore, we ensure formal privacy guarantee and analytical reliability by providing the error bound for arbitrary counting queries on the materialized views. HDPView has the following desirable properties: (a) Workload independence, (b) Analytical reliability, (c) Noise resistance on high-dimensional data, (d) Space efficiency. To demonstrate the above properties and the suitability for data exploration, we conduct extensive experiments with eight types of range counting queries on eight real datasets. HDPView outperforms the state-of-the-art methods in these evaluations.
翻译:如何在保护隐私的同时探索高维敏感关系数据的未知特性? 我们研究如何在不同的隐私下构建一个探索的隐私保存实际观点; 现有最先进的方法没有同时满足数据探索中的以下基本属性: 工作量独立、 分析可靠性(即为每次搜索查询提供误差)、 高维数据的适用性和空间效率。 为了解决上述问题, 我们提议HDPView, 通过设计得当的循环分解对原始数据立方(即计票)产生一种差异化的私人化观点。 我们的方法是进行区隔搜索,以尽可能减少计票查询的错误,同时以不同私人方式随机选择有效的切切入点(即为每次搜索提供误差)、 分析可靠性(即为每个搜索查询提供误差)、 高维度的分解分解法(即计数 ) 分析可靠性, (c) 对高维度的查询方法进行阻断,以尽可能减少误差, 并随机测算八度数据。