データキューブとコンティンジェンシーテーブルの正確かつ効率的なプライベートリリース

敏感なデータに関する集約情報をリリースする際の中心的な問題は、出力に対してプライバシー保証を提供しながら、正確に行うことです。最近の研究は、基本的なカウントクエリ、データキューブ、コンティンジェンシーテーブルを含む線形クエリのクラスに焦点を当てています。目標は、厳密なプライバシー保証を与えつつ、出力の有用性を最大化することです。ほとんどの結果は共通のテンプレートに従います：データに適用するための「戦略」セットの線形クエリを選択し、次にこれらのクエリへのノイズのある回答を使用して、関心のあるクエリを再構築します。これは、クエリに対して良好であると考えられる戦略セットを選択するか、すべての可能な戦略の空間を費用をかけて検索することを伴います。本論文では、正確性と効率のバランスを取る新しいアプローチを提案します：いくつかの戦略クエリに対して他のクエリよりも正確に回答することで、与えられたクエリセットの正確性を向上させる方法を示します。これにより、ウェーブレット、階層、フーリエ係数などの多くの人気戦略に対して効率的な最適ノイズ配分が実現されます。重要な場合の周辺クエリについては、これが以前の方法を厳密に改善することを示します。私たちの結果は、返されるクエリ回答が（未知の）データセットと最小限のコストで整合することを保証することにも拡張されます。