論文の概要: Fast and Optimal Differentially Private Frequent-Substring Mining

• arxiv url: http://arxiv.org/abs/2603.09166v1
• Date: Tue, 10 Mar 2026 04:04:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-11 15:25:24.020804
• Title: Fast and Optimal Differentially Private Frequent-Substring Mining
• Title（参考訳）: 高速かつ最適な個人周波数サブストリングマイニング
• Authors: Peaker Guo, Rayne Holland, Hao Wu,
• Abstract要約: ユーザ分散文字列のデータセットが$n$で、各長さが$ell$である場合、重要な問題は、すべての頻繁な呼び出しを識別する方法である。 我々は,空間複雑性を低減しつつ,ほぼ最適な誤差保証を保った新しい$varepsilon$-differentially privateアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 2.451701057085567
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a dataset of $n$ user-contributed strings, each of length at most $\ell$, a key problem is how to identify all frequent substrings while preserving each user's privacy. Recent work by Bernardini et al. (PODS'25) introduced a $\varepsilon$-differentially private algorithm achieving near-optimal error, but at the prohibitive cost of $O(n^2\ell^4)$ space and processing time. In this work, we present a new $\varepsilon$-differentially private algorithm that retains the same near-optimal error guarantees while reducing space complexity to $O(n \ell+ |Σ| )$ and time complexity to $O(n \ell\log |Σ| + |Σ| )$, for input alphabet $Σ$. Our approach builds on a top-down exploration of candidate substrings but introduces two new innovations: (i) a refined candidate-generation strategy that leverages the structural properties of frequent prefixes and suffixes, and (ii) pruning of the search space guided by frequency relations. These techniques eliminate the quadratic blow-ups inherent in prior work, enabling scalable frequent substring mining under differential privacy.
• Abstract（参考訳）: 長さが最大$$$$$ell$のデータセットが与えられた場合、ユーザのプライバシを保護しながら、すべての頻繁なサブストリングを識別する方法が重要な問題である。 Bernardini et al (PODS'25) による最近の研究は、ほぼ最適誤差を達成するために$\varepsilon$-differentially privateアルゴリズムを導入したが、禁止費用は$O(n^2\ell^4)$空間と処理時間である。 本研究では、入力アルファベット$Σ$に対して、空間複雑性を$O(n \ell+ |Σ| )$に減らし、時間複雑性を$O(n \ell\log |Σ| + |Σ| )$に減らしながら、同じ近似誤差を保証する新しい$\varepsilon$-differentially privateアルゴリズムを提案する。 私たちのアプローチは、候補のサブストリングをトップダウンで探索することに基づいていますが、新しい2つのイノベーションを導入しています。 一 頻繁な接頭辞及び接尾辞の構造的特性を利用した改良された候補生成戦略 (ii)周波数関係で導かれる探索空間のプルーニング。 これらの技術は、以前の作業に固有の二次的な爆発を排除し、微分プライバシーの下で、スケーラブルな頻繁なサブストリングマイニングを可能にする。

関連論文リスト

• Private Continual Counting of Unbounded Streams [11.941250828872189]
  入力サイズ$n$が予め分かっていないような非有界な環境では、差分プライベートな連続数え上げの問題について検討する。 一般的な2倍のトリックを使用すると、$n$の知識は避けられるが、最適でないエラーと非滑らかなエラーにつながる。 先行研究で研究された関数 $frac1sqrt1-z$ の対数摂動に基づく新しい行列分解を導入する。
  論文  参考訳（メタデータ） (2025-06-17T23:09:53Z)
• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
  ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。 本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。 ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
  論文  参考訳（メタデータ） (2025-05-29T17:21:20Z)
• Differentially Private Set Representations [13.576656322669098]
  本研究では,大宇宙からの大きさの集合を$k$で表すために,差分プライベート(DP)機構の問題を考察する。 最初の構成では、$(epsilon,delta)$-DP表現を生成し、エラー確率は1/(eepsilon + 1)$で、少なくとも1.05 k epsilon cdot log(e)$ bitsで空間を使用する。 また、最大$k epsilon cdot log(e)$ bitsの空間を用いて、同じエラーを持つ純粋な$epsilon$-DP表現のための第2のアルゴリズムも提示する。
  論文  参考訳（メタデータ） (2025-01-28T03:29:00Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。 本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
  論文  参考訳（メタデータ） (2024-11-27T00:48:48Z)
• Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning [2.2083091880368855]
  差分的にプライベートな$k$選択問題について検討し、$d$アイテムから最も高いスコアを持つ$k$アイテムの列を特定することを目的とした。 Gillenwaterらによる最近の研究(ICML '22)は、$d,Theta(k)$ possible length-$k$ sequencesの膨大なコレクションから直接サンプリングアプローチを採用している。 時間と空間の複雑さを持つアルゴリズムを改良し、$O(d + k2 / epsilon cdot ln d)$で、$epsilon$はプライバシーを表す。
  論文  参考訳（メタデータ） (2024-11-14T16:06:13Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)

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

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