論文の概要: On Differentially Private String Distances

• arxiv url: http://arxiv.org/abs/2411.05750v1
• Date: Fri, 08 Nov 2024 18:10:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-11 14:56:11.669502
• Title: On Differentially Private String Distances
• Title（参考訳）: 微分プライベート文字列距離について
• Authors: Jerry Yao-Chieh Hu, Erzhi Liu, Han Liu, Zhao Song, Lichen Zhang,
• Abstract要約: 基本的なデータ構造タスクは、データベース内のすべての文字列で、与えられたクエリのBin 0,1n$間の距離を見積もることである。 本稿では,このようなタスクに対して,ハミングと編集距離に着目した差分プライベート(DP)データ構造を提案する。 そこで我々は,ビットフリップ法としてランダム化応答手法の新たな適応により,これらの結果を得た。
• 参考スコア（独自算出の注目度）: 12.852131074558057
• License:
• Abstract: Given a database of bit strings $A_1,\ldots,A_m\in \{0,1\}^n$, a fundamental data structure task is to estimate the distances between a given query $B\in \{0,1\}^n$ with all the strings in the database. In addition, one might further want to ensure the integrity of the database by releasing these distance statistics in a secure manner. In this work, we propose differentially private (DP) data structures for this type of tasks, with a focus on Hamming and edit distance. On top of the strong privacy guarantees, our data structures are also time- and space-efficient. In particular, our data structure is $\epsilon$-DP against any sequence of queries of arbitrary length, and for any query $B$ such that the maximum distance to any string in the database is at most $k$, we output $m$ distance estimates. Moreover, - For Hamming distance, our data structure answers any query in $\widetilde O(mk+n)$ time and each estimate deviates from the true distance by at most $\widetilde O(k/e^{\epsilon/\log k})$; - For edit distance, our data structure answers any query in $\widetilde O(mk^2+n)$ time and each estimate deviates from the true distance by at most $\widetilde O(k/e^{\epsilon/(\log k \log n)})$. For moderate $k$, both data structures support sublinear query operations. We obtain these results via a novel adaptation of the randomized response technique as a bit flipping procedure, applied to the sketched strings.
• Abstract（参考訳）: ビット文字列のデータベースである$A_1,\ldots,A_m\in \{0,1\}^n$が与えられた場合、基本データ構造タスクは、データベース内の全ての文字列で、与えられたクエリの$B\in \{0,1\}^n$間の距離を推定することである。 さらに、これらの距離統計を安全にリリースすることで、データベースの整合性を確保したい場合もあります。 本研究では,このタイプのタスクに対して,ハミングと編集距離に着目した差分プライベート(DP)データ構造を提案する。 強力なプライバシー保証に加えて、私たちのデータ構造は時間的かつ空間的にも効率的です。 特に、我々のデータ構造は任意の長さのクエリ列に対して$\epsilon$-DPであり、データベース内の文字列への最大距離が$k$であるような任意のクエリに対して$B$に対して$m$距離推定を出力します。 さらに、ハミング距離の場合、我々のデータ構造は$\widetilde O(mk+n)$のクエリに答え、各推定値は少なくとも$\widetilde O(k/e^{\epsilon/\log k})$; - 編集距離の場合、データ構造は$\widetilde O(mk^2+n)$のクエリに答え、各推定値は最大$\widetilde O(k/e^{\epsilon/(\log k \log n)}$で真の距離から逸脱する。 適度な$k$の場合、両方のデータ構造はサブ線形クエリ操作をサポートする。 スケッチされた文字列に適用したビットフリップ手法としてランダム化応答手法の新たな適応により,これらの結果を得る。

関連論文リスト

• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• Differentially Private Kernel Density Estimation [11.526850085349155]
  我々は、カーネル密度推定(KDE)のための洗練された微分プライベート(DP)データ構造を導入する。 類似関数 $f$ とプライベートデータセット $X サブセット mathbbRd$ が与えられた場合、我々のゴールは、任意のクエリ $yinmathbbRd$ に対して、X f(x, y)$ の $sum_x を微分プライベートな方法で近似するように$X$ を前処理することである。
  論文  参考訳（メタデータ） (2024-09-03T08:01:19Z)
• Differential Privacy of Cross-Attention with Provable Guarantee [18.331374727331077]
  我々は,クロスアテンションのプライバシセキュリティに理論的保証を与えるために,新たな差分プライバシ(DP)データ構造を設計する。 我々の結果は、ユーザが意図的にクロスアテンションシステムに攻撃できる適応的なクエリに対して堅牢である。
  論文  参考訳（メタデータ） (2024-07-20T01:02:27Z)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• Supervised Training of Conditional Monge Maps [107.78770597815242]
  最適輸送(OT)理論は、多くの可能な選択の中から確率測度を他のものにマッピングする最も効率的な方法を定義し、選択する一般的な原理を記述している。 本研究では,コンテキスト変数に条件付きOTマップの族を推定するマルチタスク手法であるCondOTを紹介する。 本研究では,CondOTの遺伝的・治療的摂動の任意の組み合わせが単一細胞に与える影響を推測する能力を示す。
  論文  参考訳（メタデータ） (2022-06-28T19:34:44Z)
• Imagined-Trailing-Whitespace-Agnostic Levenshtein Distance For Plaintext Table Detection [0.0]
  Levenshtein 距離は後続の空白を他の文字や記号と同じ扱います。 人間が2つの文字列を比較するとき、両方の文字列は無限の後続の空白でパッドされていると暗黙的に仮定する。 この期待に反すると、直感的な編集距離値が得られません。
  論文  参考訳（メタデータ） (2021-03-11T20:39:40Z)
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
  このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。 一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
  論文  参考訳（メタデータ） (2020-12-16T17:58:45Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• The Sparse Vector Technique, Revisited [67.57692396665915]
  我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。 この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。 一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-02T10:50:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。