在分散式環境中實現差分隱私與一致性的分層資料計數

Abstract

我們考慮以下的一類資料查詢問題，我們稱呼這種問題為分層資料 計數問題。在分層資料計數問題中，資料提供者會根據他們手中的資 料進行分組，例如以資料提供者的所在位置的區域作為分組方式。資 料提供者希望能在隱密並且本地進行的環境下回報他們的資料。對分 層資料計數問題進行查詢可以得到所有資料提供者在各個預先定義好 的階層架構中的數量，例如在全國、各大區、各縣中資料提供者的數 量。在這篇論文中，我們提出了分層資料計數問題並且提出了一個基 於分散式架構中的差分隱私演算法並且使得分層資料計數問題的結果 是在各個分層中都是一致的。在我們的實驗中，我們提出的演算法相 較於無一致性的本地差分隱私演算法可以有效地減少雜訊量並且對於 顯著類別的估計有較好的預測。

We consider the problem of privately and distributedly conducting a class of queries that we call hierarchical data counting. Hierarchical data count- ing partition users into groups (e.g., grouping people who locate in the same area) by the values that users own, and each user may report his value and groups in private and local settings. Hierarchical data counting queries can report the count of user values at different granularities according to a pre- defined hierarchy (e.g., geographical location of the user at the national, state, and county levels). In this paper, we introduce this problem and propose a local differential private solution that generates hierarchical data counting histograms that are consistent across all levels of the hierarchy. In our exper- iment, our solution can greatly decrease the amount of noise and give a more precise heavy-hitter estimation comparing to the local differential privacy al- gorithm without consistency.