Overlook: Differentially Private Exploratory Visualization for Big Data

差分プライバシーシステムは以下の2種類に分類できる。

Systems with per-query budgeting

差分プライバシー保護される前のデータソースに分析者が直接分析し、ノイズを加えprivacy budgetでクエリ実行を抑える方式

Budget以上の情報を得るための異なる2人のユーザーのプロトコル外での結託はプライバシー要件で想定しない

Synopsis-based systems

データソース・クエリ・total privacy budgetを考慮に入れて、特定のクエリが実行可能なsynopsisデータを生成

分析者はprivacy budgetを意識せずに任意回数、synopsisデータにクエリ可能にする

実態としては、差分プライバシーを考慮して事前に多めに用意しておいた集約結果なので、分析者の実行可能なクエリは制限される

synopsisデータの生成元はimmutableで、ノイズサンプリングは一度だけ。

例：PrivateSQL, OpenDPのexample, US Census 2020

当論文Overlookでは、Synopsis-basedの差分プライバシーシステムを提案。

バックエンドのDB, クエリエンジンはなんでもOK

histogram queries, heat maps queriesをサポート

CuratorがPrivacy parametersを事前に設定し、それを元にsynopsisデータを生成

VMwareのhilliviewという大規模分散データに対するvisualizerのextensionとしてexperimentalに導入

https://gyazo.com/d60b8d5e153b73d74aecafd238764b61

ヒストグラムに対するノイズの加え方

ナイーブにはbinごとにLap(1/ε) のノイズを加える

t個のカウントにt個の独立したラプラスノイズが追加されるので、（固定1/εスケールのラプラス分布からランダムベースでサンプリングしたノイズ）誤差は$ O(t)に収束。(ref: Private and Continual Release of Statistics (2010))

https://gyazo.com/1f3e0f57ea90b2dbe7046539a9413de1

ノイズを低減するために Boosting the accuracy of differentially private histograms through consistency(2010) で提案されたhierarchical histogramを使うことで誤差を$ O(log^2_b(t))に低減。

https://gyazo.com/662db0a396a28c50d8d810bc0b5200bb

cipepser.icon 内容全然理解できてないけど、めっちゃおもしろそう

Hillview with Overlookのデモ

https://gyazo.com/da706db26b999bb2a92866bd97c14f02