論文の概要: Accelerating Private Heavy Hitter Detection on Continual Observation Streams

• arxiv url: http://arxiv.org/abs/2507.03361v1
• Date: Fri, 04 Jul 2025 07:49:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-08 15:46:34.704204
• Title: Accelerating Private Heavy Hitter Detection on Continual Observation Streams
• Title（参考訳）: 連続観測ストリームにおけるプライベートヘビーヒッタ検出の高速化
• Authors: Rayne Holland,
• Abstract要約: 遅延更新に基づく新たな微分プライベートスケッチ技術を導入し、各ステップで出力スケッチの小さな回転部分のみを摂動・更新する。 実験の結果、スループットが250ドル向上し、リアルタイム、連続観察、アプリケーションに差分プライバシーをより実用的なものにしている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Differentially private frequency estimation and heavy hitter detection are core problems in the private analysis of data streams. Two models are typically considered: the one-pass model, which outputs results only at the end of the stream, and the continual observation model, which requires releasing private summaries at every time step. While the one-pass model allows more efficient solutions, continual observation better reflects scenarios where timely and ongoing insights are critical. In the one-pass setting, sketches have proven to be an effective tool for differentially private frequency analysis, as they can be privatized by a single injection of calibrated noise. In contrast, existing methods in the continual observation model add fresh noise to the entire sketch at every step, incurring high computational costs. This challenge is particularly acute for heavy hitter detection, where current approaches often require querying every item in the universe at each step, resulting in untenable per-update costs for large domains. To overcome these limitations, we introduce a new differentially private sketching technique based on lazy updates, which perturbs and updates only a small, rotating part of the output sketch at each time step. This significantly reduces computational overhead while maintaining strong privacy and utility guarantees. In comparison to prior art, for frequency estimation, our method improves the update time by a factor of $O(w)$ for sketches of dimension $d \times w$; for heavy hitter detection, it reduces per-update complexity from $\Omega(|U|)$ to $O(d \log w)$, where $U$ is the input domain. Experiments show a increase in throughput by a factor of~$250$, making differential privacy more practical for real-time, continual observation, applications.
• Abstract（参考訳）: データストリームのプライベート分析において、異なるプライベート周波数推定と重ヒッタ検出が中核的な問題である。 ストリームの最後にのみ結果を出力するワンパスモデルと、各ステップでプライベートなサマリーを解放する必要がある連続的な観測モデルである。 ワンパスモデルはより効率的なソリューションを可能にするが、継続的な観察は、時間的および進行中の洞察が重要となるシナリオをよりよく反映する。 ワンパス設定では、スケッチはキャリブレーションノイズの単一注入により民営化できるため、差分プライベート周波数解析に有効なツールであることが証明されている。 対照的に、継続観測モデルの既存の手法は、すべてのステップでスケッチ全体に新しいノイズを与え、高い計算コストを発生させる。 現在のアプローチでは、各ステップで宇宙のすべてのアイテムを問い合わせる必要があり、その結果、大きなドメインの更新コストが不必要になる。 これらの制限を克服するために、遅延更新に基づく新たな微分プライベートスケッチ技術を導入し、各ステップで出力スケッチの小さな回転部分のみを摂動、更新する。 これにより、強力なプライバシとユーティリティ保証を維持しながら、計算オーバーヘッドを大幅に削減できる。 先行技術と比較して、周波数推定では、本手法は、次元$d \times w$のスケッチに対して$O(w)$で更新時間を改善し、重いヒットター検出では、更新時の複雑さを$Omega(|U|)$から$O(d \log w)$に減らし、$U$は入力ドメインである。 実験の結果、スループットは250ドル程度に向上し、リアルタイム、連続観察、アプリケーションに差分プライバシーをより実用的なものにしている。

関連論文リスト

• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。 微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。 これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-02-13T02:05:45Z)
• Towards Scalable and Deep Graph Neural Networks via Noise Masking [59.058558158296265]
  グラフニューラルネットワーク(GNN)は多くのグラフマイニングタスクで顕著に成功している。 計算とストレージのコストが高いため、大きなグラフにスケールすることは困難です。 既存のモデル単純化作業と互換性のあるプラグアンドプレイモジュールであるノイズマスキング(RMask)を用いたランダムウォークを提案する。
  論文  参考訳（メタデータ） (2024-12-19T07:48:14Z)
• DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report) [17.975365337852345]
  textscDPSW-Sketchは、カウントミンスケッチに基づいたスライドウィンドウフレームワークである。 我々は、textscDPSW-Sketchが最先端の方法よりもはるかに優れたユーティリティプライバシトレードオフを提供することを示した。
  論文  参考訳（メタデータ） (2024-06-12T07:24:19Z)
• PeFAD: A Parameter-Efficient Federated Framework for Time Series Anomaly Detection [51.20479454379662]
  私たちはaを提案します。 フェデレートされた異常検出フレームワークであるPeFADは、プライバシーの懸念が高まっている。 我々は、4つの実際のデータセットに対して広範な評価を行い、PeFADは既存の最先端ベースラインを最大28.74%上回っている。
  論文  参考訳（メタデータ） (2024-06-04T13:51:08Z)
• Graph Spatiotemporal Process for Multivariate Time Series Anomaly Detection with Missing Values [67.76168547245237]
  本稿では,グラフ時間過程と異常スコアラを用いて異常を検出するGST-Proという新しいフレームワークを提案する。 実験結果から,GST-Pro法は時系列データ中の異常を効果的に検出し,最先端の手法より優れていることがわかった。
  論文  参考訳（メタデータ） (2024-01-11T10:10:16Z)
• TFMQ-DM: Temporal Feature Maintenance Quantization for Diffusion Models [52.454274602380124]
  拡散モデルは非常に時間ステップ$t$に大きく依存し、良好なマルチラウンドデノジングを実現している。 本稿では,時間情報ブロック上に構築した時間的特徴保守量子化(TFMQ)フレームワークを提案する。 先駆的なブロック設計により、時間情報認識再構成(TIAR)と有限集合キャリブレーション(FSC)を考案し、完全な時間的特徴を整列させる。
  論文  参考訳（メタデータ） (2023-11-27T12:59:52Z)
• Differentially Private Statistical Inference through $\beta$-Divergence One Posterior Sampling [2.8544822698499255]
  本稿では,モデルとデータ生成プロセス間の$beta$-divergenceの最小化を目標とした,一般化後部からの後部サンプリング手法を提案する。 これにより、基礎となるモデルの変更を必要とせずに、一般的に適用可能なプライベートな推定が可能になる。 我々は、$beta$D-Bayesが同一のプライバシー保証に対してより正確な推測を行うことを示す。
  論文  参考訳（メタデータ） (2023-07-11T12:00:15Z)
• Continual and Sliding Window Release for Private Empirical Risk Minimization [7.054093620465401]
  本稿では、最近のデータウインドウのモデルを継続的にリリースする、正規化された経験的リスク最小化アルゴリズムについて述べる。 無限の時間的地平線上でモデルをリリースしても、任意のデータポイントのプライバシコストは、一定の$epsilon$差分プライバシーによって制限される。
  論文  参考訳（メタデータ） (2022-03-07T18:44:16Z)

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

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