論文の概要: Scalable contribution bounding to achieve privacy
- arxiv url: http://arxiv.org/abs/2507.23432v1
- Date: Thu, 31 Jul 2025 11:14:17 GMT
- ステータス: 情報取得中
- システム内更新日: 2025-08-01 14:01:51.917278
- Title: Scalable contribution bounding to achieve privacy
- Title（参考訳）: プライバシーを達成するためのスケーラブルなコントリビューション
- Authors: Vincent Cohen-Addad, Alessandro Epasto, Jason Lee, Morteza Zadimoghaddam,
- Abstract要約: 現代のデータセットでは、ユーザレベルのプライバシを強制するには、各ユーザの合計コントリビューションをカプセル化する必要がある。
このタスクの既存のアルゴリズムは計算集約的であり、今日の大規模データセットにはスケールしない。
我々のアプローチは、複雑なオーナシップ構造をハイパーグラフとしてモデル化し、ユーザを頂点とし、レコードをハイパーエッジとする。
すべての所有者が全会一致で同意した場合のみ、最終データセットにレコードを追加することにより、ユーザの事前定義されたコントリビューション制限が違反しないことが保証される。
- 参考スコア（独自算出の注目度）: 62.6490768306231
- License:
- Abstract: In modern datasets, where single records can have multiple owners, enforcing user-level differential privacy requires capping each user's total contribution. This "contribution bounding" becomes a significant combinatorial challenge. Existing sequential algorithms for this task are computationally intensive and do not scale to the massive datasets prevalent today. To address this scalability bottleneck, we propose a novel and efficient distributed algorithm. Our approach models the complex ownership structure as a hypergraph, where users are vertices and records are hyperedges. The algorithm proceeds in rounds, allowing users to propose records in parallel. A record is added to the final dataset only if all its owners unanimously agree, thereby ensuring that no user's predefined contribution limit is violated. This method aims to maximize the size of the resulting dataset for high utility while providing a practical, scalable solution for implementing user-level privacy in large, real-world systems.
- Abstract（参考訳）: 単一のレコードが複数のオーナを持つ現代のデータセットでは、ユーザレベルの差分プライバシを強制するには、各ユーザの合計コントリビューションをカプセル化する必要がある。
この「コントリビューション・バウンディング」は、重要な組合せ問題となる。
このタスクの既存のシーケンシャルアルゴリズムは計算集約的であり、今日の大規模データセットにはスケールしない。
このスケーラビリティのボトルネックに対処するために、我々は新しく効率的な分散アルゴリズムを提案する。
我々のアプローチは、複雑なオーナシップ構造をハイパーグラフとしてモデル化し、ユーザを頂点とし、レコードをハイパーエッジとする。
アルゴリズムはラウンドで進み、ユーザーは並列にレコードを提案できる。
すべての所有者が全会一致で同意した場合のみ、最終データセットにレコードを追加することにより、ユーザの事前定義されたコントリビューション制限が違反しないことが保証される。
本手法は,大規模で現実的なシステムにおいて,ユーザレベルのプライバシを実装するための実用的でスケーラブルなソリューションを提供しながら,結果として得られるデータセットのサイズを最大化することを目的とする。
関連論文リスト
- SKALD: Scalable K-Anonymisation for Large Datasets [4.1034194672472575]
SKALDは、RAMに制限のある大規模なデータセット上でk匿名化を実行するための新しいアルゴリズムである。
提案アルゴリズムは,k-匿名化方式よりも複数倍の性能向上を実現する。
論文 参考訳（メタデータ） (2025-05-06T13:38:53Z) - Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。
目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。
そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元するアルゴリズムであるMaximumDegree (MAD)を提案する。
論文 参考訳（メタデータ） (2025-02-13T01:27:11Z) - User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。
近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。
ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
論文 参考訳（メタデータ） (2023-09-21T21:51:55Z) - Mean Estimation with User-level Privacy under Data Heterogeneity [54.07947274508013]
異なるユーザーは、非常に多くの異なるデータポイントを持っているかもしれない。
すべてのユーザが同じディストリビューションからサンプルを採取していると仮定することはできない。
本研究では,データの分布と量の両方でユーザデータが異なる異質なユーザデータの単純なモデルを提案する。
論文 参考訳（メタデータ） (2023-07-28T23:02:39Z) - Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
大規模未ラベルデータから学ぶための2つの戦略を提案する。
第1の戦略は、近傍関係に違反することなく、それぞれのデータセットサイズを減らすために、局所的な近傍サンプリングを行う。
第2の戦略は、低時間上限の複雑さを持ち、メモリの複雑さを O(n2) から O(kn) に k n で還元する新しい再帰的手法を利用する。
論文 参考訳（メタデータ） (2023-07-26T16:19:19Z) - Algorithms for bounding contribution for histogram estimation under
user-level privacy [37.406400590568644]
ユーザレベルの差分プライバシー下でのヒストグラム推定の問題点について検討する。
目標は、単一のユーザのすべてのエントリのプライバシを維持することだ。
ヒストグラム推定のための最適なユーザコントリビューションを選択するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-07T04:53:24Z) - Meta Clustering Learning for Large-scale Unsupervised Person
Re-identification [124.54749810371986]
メタクラスタリング学習(MCL)と呼ばれる「大規模タスクのための小さなデータ」パラダイムを提案する。
MCLは、第1フェーズのトレーニングのためにコンピューティングを節約するためにクラスタリングを介して、未ラベルデータのサブセットを擬似ラベル付けするのみである。
提案手法は計算コストを大幅に削減すると同時に,従来よりも優れた性能を実現している。
論文 参考訳（メタデータ） (2021-11-19T04:10:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。