論文の概要: An Iconic Heavy Hitter Algorithm Made Private

• arxiv url: http://arxiv.org/abs/2512.17295v1
• Date: Fri, 19 Dec 2025 07:20:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-22 19:25:54.282313
• Title: An Iconic Heavy Hitter Algorithm Made Private
• Title（参考訳）: イコニックヘビーヒッターのアルゴリズムがプライベートに
• Authors: Rayne Holland,
• Abstract要約: データストリームにおける重いヒットターの特定は、現代の分析システムにおける広範なアプリケーションにおいて、根本的な問題である。 本研究では,SpaceSavingアルゴリズムの最初の微分プライベートな変種について述べる。 本稿では,データストリームモデルにおける任意の微分プライベート周波数オラクルから重ヒッタを抽出する汎用手法を提案する。
• 参考スコア（独自算出の注目度）: 0.45357961994031076
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Identifying heavy hitters in data streams is a fundamental problem with widespread applications in modern analytics systems. These streams are often derived from sensitive user activity, making update-level privacy guarantees necessary. While recent work has adapted the classical heavy hitter algorithm Misra-Gries to satisfy differential privacy in the streaming model, the privatization of other heavy hitter algorithms with better empirical utility is absent. Under this observation, we present the first differentially private variant of the SpaceSaving algorithm, which, in the non-private setting, is regarded as the state-of-the-art in practice. Our construction post-processes a non-private SpaceSaving summary by injecting asymptotically optimal noise and applying a carefully calibrated selection rule that suppresses unstable labels. This yields strong privacy guarantees while preserving the empirical advantages of SpaceSaving. Second, we introduce a generic method for extracting heavy hitters from any differentially private frequency oracle in the data stream model. The method requires only O(k) additional memory, where k is the number of heavy items, and provides a mechanism for safely releasing item identities from noisy frequency estimates. This yields an efficient, plug-and-play approach for private heavy hitter recovery from linear sketches. Finally, we conduct an experimental evaluation on synthetic and real-world datasets. Across a wide range of privacy parameters and space budgets, our method provides superior utility to the existing differentially private Misra-Gries algorithm. Our results demonstrate that the empirical superiority of SpaceSaving survives privatization and that efficient, practical heavy hitter identification is achievable under strong differential privacy guarantees.
• Abstract（参考訳）: データストリームにおける重いヒットターの特定は、現代の分析システムにおける広範なアプリケーションにおいて、根本的な問題である。 これらのストリームは、しばしばセンシティブなユーザーアクティビティから派生し、更新レベルのプライバシーを保証する必要がある。 近年の研究では、ストリーミングモデルにおける差分プライバシを満たすために、古典的なヘビーヒッターアルゴリズムであるMisra-Griesが採用されているが、より優れた経験的有用性を備えた他のヘビーヒッターアルゴリズムの民営化は欠落している。 本研究は,SpaceSavingアルゴリズムにおいて,非プライベートな環境では,実際に最先端技術とみなす最初の微分プライベートな変種を提示する。 提案手法は,漸近的最適雑音を注入し,不安定なラベルを抑えるための慎重に調整された選択規則を適用することで,非プライベートなSpaceSavingサマリーを後処理する。 これにより、SpaceSavingの実証的な利点を維持しながら、強力なプライバシー保証が得られる。 第2に,データストリームモデルにおける任意の微分プライベート周波数オラクルから重ヒットタを抽出する汎用手法を提案する。 この方法は、kが重いアイテムの数であるO(k)追加メモリのみを必要とし、ノイズの多い周波数推定値からアイテムのIDを安全に解放するメカニズムを提供する。 これにより、線形スケッチからプライベートヘビーヒッタリカバリのための効率的なプラグアンドプレイアプローチが得られる。 最後に,合成および実世界のデータセットを実験的に評価する。 プライバシパラメータや空間予算の広い範囲において,本手法は既存の微分プライベートなMisra-Griesアルゴリズムよりも優れている。 以上の結果から,SpaceSavingの実証的な優位性は民営化に留まり,高い差分プライバシー保証の下では,効果的で実用的な重ヒットター識別が達成可能であることが示された。

関連論文リスト

• Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regression [22.733602577854825]
  差分プライバシー制約下でのインストゥルメンタル変数回帰(IVaR)について検討する。 勾配更新に慎重に校正された雑音を注入することにより、差分プライバシーを確保するノイズの多い2状態勾配降下アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-09-26T18:02:58Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。 微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。 これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-02-13T02:05:45Z)
• Differentially Private Random Feature Model [47.35176457481132]
  プライバシを保存するカーネルマシンに対して,差分的にプライベートな特徴モデルを作成する。 本手法は,プライバシを保護し,一般化誤差を導出する。
  論文  参考訳（メタデータ） (2024-12-06T05:31:08Z)
• Differentially private and decentralized randomized power method [15.955127242261808]
  本稿では,ランダム化電力法におけるプライバシー保護の強化について述べる。 まず、微分プライバシーを実現するために、現在の技術で必要とされるノイズの量を削減できる変種を提案する。 次に、データを複数のユーザ間で分散する分散フレームワークに適用する。
  論文  参考訳（メタデータ） (2024-11-04T09:53:03Z)
• On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。 差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。 アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
  論文  参考訳（メタデータ） (2023-02-11T14:45:31Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。 本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-07-13T17:09:25Z)
• Private measures, random walks, and synthetic data [7.5764890276775665]
  微分プライバシーは、情報理論のセキュリティ保証を提供する数学的概念である。 我々は、プライベートな合成データを効率的に構築できるデータセットからプライベートな尺度を開発する。 我々の構築における重要な要素は、独立確率変数と同様の連立分布を持つ新しい超規則ランダムウォークである。
  論文  参考訳（メタデータ） (2022-04-20T00:06:52Z)
• Robust and Differentially Private Mean Estimation [40.323756738056616]
  異なるプライバシーは、米国国勢調査から商用デバイスで収集されたデータまで、さまざまなアプリケーションで標準要件として浮上しています。 このようなデータベースの数は、複数のソースからのデータからなり、それらすべてが信頼できるわけではない。 これにより、既存のプライベート分析は、腐敗したデータを注入する敵による攻撃に弱い。
  論文  参考訳（メタデータ） (2021-02-18T05:02:49Z)

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

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