論文の概要: Differentially Private Substring and Document Counting
- arxiv url: http://arxiv.org/abs/2412.13813v1
- Date: Wed, 18 Dec 2024 13:00:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-19 13:22:32.788043
- Title: Differentially Private Substring and Document Counting
- Title（参考訳）: 異なるプライベートなサブストリングと文書カウント
- Authors: Giulia Bernardini, Philip Bille, Inge Li Gørtz, Teresa Anna Steiner,
- Abstract要約: 我々は、この問題をすべてのパターンに対して同時に解くために、$epsilon$-differentially privateデータ構造を与えます。
本研究では,独立した関心を持つ木上での数え上げ関数の一般クラスを微分的にプライベートに計算する新しい手法を開発した。
- 参考スコア（独自算出の注目度）: 0.8581825056575687
- License:
- Abstract: Differential privacy is the gold standard for privacy in data analysis. In many data analysis applications, the data is a database of documents. For databases consisting of many documents, one of the most fundamental problems is that of pattern matching and computing (i) how often a pattern appears as a substring in the database (substring counting) and (ii) how many documents in the collection contain the pattern as a substring (document counting). In this paper, we initiate the theoretical study of substring and document counting under differential privacy. We give an $\epsilon$-differentially private data structure solving this problem for all patterns simultaneously with a maximum additive error of $O(\ell \cdot\mathrm{polylog}(n\ell|\Sigma|))$, where $\ell$ is the maximum length of a document in the database, $n$ is the number of documents, and $|\Sigma|$ is the size of the alphabet. We show that this is optimal up to a $O(\mathrm{polylog}(n\ell))$ factor. Further, we show that for $(\epsilon,\delta)$-differential privacy, the bound for document counting can be improved to $O(\sqrt{\ell} \cdot\mathrm{polylog}(n\ell|\Sigma|))$. Additionally, our data structures are efficient. In particular, our data structures use $O(n\ell^2)$ space, $O(n^2\ell^4)$ preprocessing time, and $O(|P|)$ query time where $P$ is the query pattern. Along the way, we develop a new technique for differentially privately computing a general class of counting functions on trees of independent interest. Our data structures immediately lead to improved algorithms for related problems, such as privately mining frequent substrings and $q$-grams. For $q$-grams, we further improve the preprocessing time of the data structure.
- Abstract（参考訳）: 差分プライバシーは、データ分析におけるプライバシのゴールドスタンダードである。
多くのデータ分析アプリケーションでは、データはドキュメントのデータベースである。
多くの文書からなるデータベースの場合、最も根本的な問題の1つはパターンマッチングと計算である。
(i)データベースのサブストリングとしてパターンが出現する頻度(サブストリングカウント)
(ii) サブストリング(文書カウント)としてのパターンを含む文書がいくつあるか。
本稿では,差分プライバシー下でのサブストリングと文書カウントに関する理論的研究を開始する。
O(\ell \cdot\mathrm{polylog}(n\ell|\Sigma|))$,$\ell$はデータベース内のドキュメントの最大長、$n$はドキュメントの数、$|\Sigma|$はアルファベットのサイズである。
これは$O(\mathrm{polylog}(n\ell))$ factorまで最適であることを示す。
さらに、$(\epsilon,\delta)$-differential privacyの場合、ドキュメントカウントのバウンドは$O(\sqrt{\ell} \cdot\mathrm{polylog}(n\ell|\Sigma|))$に改善できる。
さらに、データ構造は効率的です。
特に、我々のデータ構造では、$O(n\ell^2)$ space, $O(n^2\ell^4)$ preprocessing time, $O(|P|)$ query time ここで$P$はクエリパターンです。
そこで本研究では,興味ある木上での数え上げ関数の一般クラスを微分プライベートに計算する新しい手法を開発した。
私たちのデータ構造は、プライベートに頻繁にサブストリングをマイニングしたり、$q$-gramといった、関連する問題に対するアルゴリズムの改善につながります。
$q$-gramsの場合、データ構造の前処理時間をさらに改善します。
関連論文リスト
- On Differentially Private String Distances [12.852131074558057]
基本的なデータ構造タスクは、データベース内のすべての文字列で、与えられたクエリのBin 0,1n$間の距離を見積もることである。
本稿では,このようなタスクに対して,ハミングと編集距離に着目した差分プライベート(DP)データ構造を提案する。
そこで我々は,ビットフリップ法としてランダム化応答手法の新たな適応により,これらの結果を得た。
論文 参考訳（メタデータ） (2024-11-08T18:10:07Z) - Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Differential Privacy of Cross-Attention with Provable Guarantee [18.331374727331077]
我々は,クロスアテンションのプライバシセキュリティに理論的保証を与えるために,新たな差分プライバシ(DP)データ構造を設計する。
我々の結果は、ユーザが意図的にクロスアテンションシステムに攻撃できる適応的なクエリに対して堅牢である。
論文 参考訳（メタデータ） (2024-07-20T01:02:27Z) - On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。
この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
論文 参考訳（メタデータ） (2024-06-24T04:06:09Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Continual Counting with Gradual Privacy Expiration [15.87191465142231]
提案アルゴリズムは,大規模なプライバシー有効期限関数に対して,O(log(T)/epsilon)$の加算誤差を実現する。
我々の経験的評価は、自然ベースラインアルゴリズムよりも大きな値の$d$に対する経験的プライバシ損失が著しく小さく、徐々に増加するプライバシー損失を達成していることを示している。
論文 参考訳（メタデータ） (2024-06-06T07:20:16Z) - Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。
我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。
ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-06-01T07:33:41Z) - Differentially Private Approximate Pattern Matching [0.0]
我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。
目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。
1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
論文 参考訳（メタデータ） (2023-11-13T15:53:45Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - The Sparse Vector Technique, Revisited [67.57692396665915]
我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。
この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。
一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-02T10:50:52Z) - Differentially Private Set Union [23.001440922454407]
差分プライバシーのグローバルモデルにおけるセットユニオンの基本動作について検討する。
この問題では、無限の大きさのアイテムが$U$で、データベースが$D$である。
我々は、$S のサブセットである cup_i W_i$ を出力する(epsilon$,$delta$)-微分プライベートなアルゴリズムを望んでいる。
論文 参考訳（メタデータ） (2020-02-22T18:33:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。