Differential Private-Hilbert: Data Publication Using Hilbert Curve Spatial Mapping

摘要

A high demand exists in publishing data that preserves privacy. A common method that ensures privacy is Differential Privacy which perturbs the data based on the Laplace distribution prior to disseminating the data. Proposed techniques suffer from data having many attributes or high dimensional data known as the curse of dimensionality. A problem exists with both, accuracy and processing resources when handling large amounts of high dimensional data. The method, Differential Private-Hilbert, being presented is an initial study whose goal is to achieve ε-differential privacy. An algorithm is proposed for answering range queries over high dimensional data. The data is mapped into 1-dimensional tuples using Hilbert curves and partitioned into groups. The data are stored in a tree structure whose leaf nodes are abstracted to a histogram and calibrated noise is then injected. The clustering property of Hilbert curves is exploited to improve the accuracy of the published data. The tree structure lends itself for efficient access to store and process range-count queries. DP-Hilbert requires minimal computing resources. An accuracy and run-time performance study is done on multi-dimensional data by measuring the Mean Squared Error (MSE) and CPU processing time. Large synthetic datasets having between 3 to 8 dimensions are evaluated.