論文の概要: Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model

• arxiv url: http://arxiv.org/abs/2505.23682v1
• Date: Thu, 29 May 2025 17:21:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-30 18:14:08.03092
• Title: Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model
• Title（参考訳）: 旋回型モデルにおける離散要素推定のための微分プライベートな空間効率アルゴリズム
• Authors: Rachel Cummings, Alessandro Epasto, Jieming Mao, Tamalika Mukherjee, Tingting Ou, Peilin Zhong,
• Abstract要約: ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。 本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。 ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
• 参考スコア（独自算出の注目度）: 61.40326886123332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The turnstile continual release model of differential privacy captures scenarios where a privacy-preserving real-time analysis is sought for a dataset evolving through additions and deletions. In typical applications of real-time data analysis, both the length of the stream $T$ and the size of the universe $|U|$ from which data come can be extremely large. This motivates the study of private algorithms in the turnstile setting using space sublinear in both $T$ and $|U|$. In this paper, we give the first sublinear space differentially private algorithms for the fundamental problem of counting distinct elements in the turnstile streaming model. Our algorithm achieves, on arbitrary streams, $\tilde{O}_{\eta}(T^{1/3})$ space and additive error, and a $(1+\eta)$-relative approximation for all $\eta \in (0,1)$. Our result significantly improves upon the space requirements of the state-of-the-art algorithms for this problem, which is linear, approaching the known $\Omega(T^{1/4})$ additive error lower bound for arbitrary streams. Moreover, when a bound $W$ on the number of times an item appears in the stream is known, our algorithm provides $\tilde{O}_{\eta}(\sqrt{W})$ additive error, using $\tilde{O}_{\eta}(\sqrt{W})$ space. This additive error asymptotically matches that of prior work which required instead linear space. Our results address an open question posed by [Jain, Kalemaj, Raskhodnikova, Sivakumar, Smith, Neurips23] about designing low-memory mechanisms for this problem. We complement these results with a space lower bound for this problem, which shows that any algorithm that uses similar techniques must use space $\tilde{\Omega}(T^{1/3})$ on arbitrary streams.
• Abstract（参考訳）: 差分プライバシーのターンタイル連続リリースモデルは、追加や削除を通じて進化するデータセットのために、プライバシを保存するリアルタイム分析を求めるシナリオをキャプチャする。 リアルタイムデータ解析の典型的な応用では、ストリームの長さ$T$と宇宙のサイズ$|U|$の両方で、そこから来るデータは非常に大きい。 これは、空間部分線型を用いたターンタイル設定におけるプライベートアルゴリズムの研究を、$T$と$|U|$の両方で動機付ける。 本稿では、ターンタイルストリーミングモデルにおいて、異なる要素をカウントする基本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを提案する。 我々のアルゴリズムは任意のストリームに対して$\tilde{O}_{\eta}(T^{1/3})$空間と加法誤差、および$1+\eta)$-relative approximation for all $\eta \in (0,1)$を達成する。 この結果は、線形である問題に対する最先端アルゴリズムの空間要求を大幅に改善し、既知の$\Omega(T^{1/4})$ additive error lower bound for arbitrary stream に近づいた。 さらに、ストリームにアイテムが現れる回数について有界な$W$が分かっている場合、我々のアルゴリズムは$\tilde{O}_{\eta}(\sqrt{W})$加法誤差を$\tilde{O}_{\eta}(\sqrt{W})$ space を用いて提供する。 この加法誤差は、代わりに線型空間を必要とする前の作業と漸近的に一致する。 我々の結果は,[Jain, Kalemaj, Raskhodnikova, Sivakumar, Smith, Neurips23]によって提起された,この問題に対する低メモリ機構の設計に関するオープンな疑問に対処する。 同様の手法を使用するアルゴリズムは任意のストリームに対して空間 $\tilde{\Omega}(T^{1/3})$ を使わなければならないことを示す。

関連論文リスト

• Differentially Private Clustering in Data Streams [65.78882209673885]
  オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。 我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [9.29659220237395]
  本稿では,相関クラスタリングの解法を提案する。 我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。 提案手法の主な要素はスパース線グラフ分解への新規な接続である。
  論文  参考訳（メタデータ） (2021-09-29T16:25:02Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• A Deterministic Streaming Sketch for Ridge Regression [15.256452294422294]
  リッジ回帰を推定するための決定論的空間効率アルゴリズムを提案する。 これは、ソリューションエラーが保証された最初の$o(d2)$空間決定論的ストリーミングアルゴリズムである。 合成データセットと実世界のデータセットのランダムなスケッチアルゴリズムと比較して、我々のアルゴリズムは空間と類似時間が少なくて経験的誤差が少ない。
  論文  参考訳（メタデータ） (2020-02-05T22:08:29Z)

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

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