論文の概要: DP-S4S: Accurate and Scalable Select-Join-Aggregate Query Processing with User-Level Differential Privacy

• arxiv url: http://arxiv.org/abs/2603.14994v1
• Date: Mon, 16 Mar 2026 08:58:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 18:28:57.89082
• Title: DP-S4S: Accurate and Scalable Select-Join-Aggregate Query Processing with User-Level Differential Privacy
• Title（参考訳）: DP-S4S: ユーザレベル差分プライバシによる正確でスケーラブルなSelect-Join-Aggregateクエリ処理
• Authors: Yuan Qiu, Xiaokui Xiao, Yin Yang,
• Abstract要約: DPを用いたSelect-Join-Aggregateクエリは、さまざまな領域において重要なアプリケーションにおいて基本的な問題である。 スケーラビリティを実現するための有望な方向の1つは、サンプリングを通じて、結果のユーティリティと計算コストのトレードオフを提供する。 本稿では,これらの課題に対処する新しいメカニズムであるDP-S4Sを提案する。
• 参考スコア（独自算出の注目度）: 27.30691895786047
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Answering Select-Join-Aggregate queries with DP is a fundamental problem with important applications in various domains. The current SOTA methods ensure user-level DP (i.e., the adversary cannot infer the presence or absence of any given individual user with high confidence) and achieve instance-optimal accuracy on the query results. However, these solutions involve solving expensive optimization programs, which may incur prohibitive computational overhead for large databases. One promising direction to achieve scalability is through sampling, which provides a tunable trade-off between result utility and computational costs. However, applying sampling to differentially private SJA processing is a challenge for two reasons. First, it is unclear what to sample, in order to achieve the best accuracy within a given computational budget. Second, prior solutions were not designed with sampling in mind, and their mathematical tool chains are not sampling-friendly. To our knowledge, the only known solution that applies sampling to private SJA processing is S&E, a recent proposal that (i) samples users and (ii) combines sampling directly with existing solutions to enforce DP. We show that both are suboptimal designs; consequently, even with a relatively high sample rate, the error incurred by S&E can be 10x higher than the underlying DP mechanism without sampling. Motivated by this, we propose Differentially Private Sampling for Scale (DP-S4S), a novel mechanism that addresses the above challenges by (i) sampling aggregation units instead of users, and (ii) laying the mathematical foundation for SJA processing under RDP, which composes more easily with sampling. Further, DP-S4S can answer both scalar and vector SJA queries. Extensive experiments on real data demonstrate that DP-S4S enables scalable SJA processing on large datasets under user-level DP, while maintaining high result utility.
• Abstract（参考訳）: DPを用いたSelect-Join-Aggregateクエリの解答は、さまざまな領域における重要なアプリケーションにおいて、根本的な問題である。 現在のSOTA方式は、ユーザレベルのDP(すなわち、特定のユーザの有無を高い信頼性で推測できない)を保証し、クエリ結果のインスタンス-最適精度を達成する。 しかし、これらのソリューションは高価な最適化プログラムを解くことを含み、大規模なデータベースでは計算オーバーヘッドが禁じられる可能性がある。 スケーラビリティを実現するための有望な1つの方向は、サンプリングを通じて、結果のユーティリティと計算コストの間の調整可能なトレードオフを提供する。 しかし,SJA処理にサンプリングを適用することは2つの理由により困難である。 第一に、与えられた計算予算内で最高の精度を達成するために、何をサンプリングすべきかは不明確である。 第二に、事前のソリューションはサンプリングを念頭に設計されておらず、数学的ツールチェーンはサンプリングに適さない。 我々の知る限り、サンプリングをプライベートなSJA処理に適用する唯一の方法がS&Eである。 (i)ユーザとサンプル (ii)サンプリングと既存のソリューションを直接組み合わせてDPを強制する。 その結果,S&Eによる誤差はサンプリングを伴わないDP機構よりも10倍高い値が得られることがわかった。 これを動機として、上記の課題に対処する新しいメカニズムであるDP-S4S(differially Private Smpling for Scale)を提案する。 一 利用者の代わりに集積単位を採取すること。 (II) SJA 処理の数学的基礎を RDP で構築し, サンプリングによりより容易に構成できる。 さらに、DP-S4SはスカラーとベクトルSJAクエリの両方に答えることができる。 DP-S4Sは、ユーザレベルのDPの下で大きなデータセット上でスケーラブルなSJA処理が可能であり、高い結果のユーティリティを維持できることを示す。

関連論文リスト

• DP-SPRT: Differentially Private Sequential Probability Ratio Tests [18.783606628556342]
  我々は、プライバシー制約の下で2つの単純な仮説のシーケンシャルなテストのために、ウォルドの有名なシークエンシャル確率比テストを再検討する。 所望のエラー確率とプライバシ制約を達成するために校正可能なラッパーであるDP-SPRTを提案する。
  論文  参考訳（メタデータ） (2025-08-08T15:09:13Z)
• SPARE: Single-Pass Annotation with Reference-Guided Evaluation for Automatic Process Supervision and Reward Modelling [58.05959902776133]
  私たちはSingle-Passを紹介します。 Reference-Guided Evaluation (SPARE)は、効率的なステップごとのアノテーションを可能にする新しい構造化フレームワークである。 数学的推論(GSM8K, MATH)、マルチホップ質問応答(MuSiQue-Ans)、空間推論(SpaRP)にまたがる4つの多様なデータセットにおけるSPAREの有効性を実証する。 ProcessBenchでは、SPAREがデータ効率のよいアウト・オブ・ディストリビューションの一般化を実証し、トレーニングサンプルの$sim$16%しか使用していない。
  論文  参考訳（メタデータ） (2025-06-18T14:37:59Z)
• ConSol: Sequential Probability Ratio Testing to Find Consistent LLM Reasoning Paths Efficiently [3.6393221632527686]
  小言語モデル(LLM)は、回答を提供する前に中間推論ステップを生成することで複雑なタスクを解決する。 広く使われている自己整合性法は、精度を向上させるために複数の推論経路を集約することにより、これらのコストをさらに高める。 十分な整合性が達成できればサンプリングを動的に停止するために,逐次確率比検定(SPRT)を活用することを提案する。
  論文  参考訳（メタデータ） (2025-03-22T00:07:28Z)
• Towards Optimal Multi-draft Speculative Decoding [102.67837141152232]
  MDSD(Multi-Draft Speculative Decoding)は、各トークンを生成する際に、小さなドラフトモデルで複数のドラフトを生成する手法である。 本稿では、最適輸送問題の双対性について論じ、最適受容率を効率的に計算する方法を提供する。
  論文  参考訳（メタデータ） (2025-02-26T03:22:44Z)
• Scaling LLM Inference with Optimized Sample Compute Allocation [56.524278187351925]
  我々は、異なる推論構成の最適な混合を見つけるアルゴリズムであるOSCAを提案する。 実験の結果,学習した混合アロケーションでは,最高の単一構成よりも精度がよいことがわかった。 OSCAはシングルターンタスク以外のエージェント処理にも有効であることが示されており、デフォルト設定よりも3倍少ない計算でSWE-Benchの精度が向上している。
  論文  参考訳（メタデータ） (2024-10-29T19:17:55Z)
• How Private are DP-SGD Implementations? [61.19794019914523]
  2種類のバッチサンプリングを使用する場合、プライバシ分析の間に大きなギャップがあることが示される。 その結果,2種類のバッチサンプリングでは,プライバシ分析の間に大きなギャップがあることが判明した。
  論文  参考訳（メタデータ） (2024-03-26T13:02:43Z)
• Salience DETR: Enhancing Detection Transformer with Hierarchical Salience Filtering Refinement [19.277560848076984]
  2段階の選択戦略は、選択したクエリとオブジェクトのミスマッチによるスケールバイアスと冗長性をもたらす。 本稿では,フィルタされた識別クエリのみにトランスフォーマーを符号化する階層型サリエンスフィルタリング精細化を提案する。 提案されたSalience DETRは、課題固有の3つのデータセットに対して、+4.0% AP、+0.2% AP、+4.4% APを大幅に改善する。
  論文  参考訳（メタデータ） (2024-03-24T13:01:57Z)
• Weighted Sparse Partial Least Squares for Joint Sample and Feature Selection [7.219077740523681]
  本稿では, 共同サンプルと特徴選択のために, $ell_infty/ell_0$-norm制約付きスパースPSS(ell_infty/ell_$-wsPLS)法を提案する。 我々は,各マルチビューwsPLSモデルに対して効率的な反復アルゴリズムを開発し,その収束性を示す。
  論文  参考訳（メタデータ） (2023-08-13T10:09:25Z)
• One-Dimensional Deep Image Prior for Curve Fitting of S-Parameters from Electromagnetic Solvers [57.441926088870325]
  Deep Image Prior(ディープ・イメージ・プライオリ、ディープ・イメージ・プライオリ、DIP)は、ランダムなd畳み込みニューラルネットワークの重みを最適化し、ノイズや過度な測定値からの信号に適合させる技術である。 本稿では,Vector Fitting (VF) の実装に対して,ほぼすべてのテスト例において優れた性能を示す。
  論文  参考訳（メタデータ） (2023-06-06T20:28:37Z)
• Pareto Optimization for Active Learning under Out-of-Distribution Data Scenarios [79.02009938011447]
  本研究では,未ラベルデータプールからバッチサイズを固定した未ラベルサンプルの最適なサブセットを選択するサンプリング手法を提案する。 実験の結果,従来の機械学習(ML)タスクとディープラーニング(DL)タスクの両方において,その効果が示された。
  論文  参考訳（メタデータ） (2022-07-04T04:11:44Z)
• DeepSampling: Selectivity Estimation with Predicted Error and Response Time [7.23389716633927]
  本稿では,サンプルベースAQPアルゴリズムの精度を予測するディープラーニングモデルであるDeepSamplingを提案する。 DeepSamplingは、既存の空間データベースがAQPの精度を制御するための信頼性の高いツールを提供する最初のシステムである。
  論文  参考訳（メタデータ） (2020-08-16T03:23:01Z)

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

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