論文の概要: Online Differentially Private Consistent Clustering

• arxiv url: http://arxiv.org/abs/2608.27896v1
• Date: Fri, 28 Aug 2026 04:03:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-31 17:16:04.200114
• Title: Online Differentially Private Consistent Clustering
• Title（参考訳）: オンライン差分的一貫性クラスタリング
• Abstract要約: オンラインストリーミング環境における差分プライベート(DP)$k$-meansと$k$-medianクラスタリングについて検討した。 入力ストリームの半コアセットであるプライベートストリームに(感性)入力ストリームを変換する汎用的なリダクションを与える。
• 参考スコア（独自算出の注目度）: 75.99116543456606
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study differentially private (DP) $k$-means and $k$-median clustering in the online streaming setting. In this model, points arrive sequentially, and at each time step, we need to output a set of $k$ centers that optimizes the clustering objective for all points seen so far. We give a generic reduction that transforms the (sensitive) input stream into a private stream, which is a semi-coreset of the input stream. This implies that any (non-private) online clustering algorithm, run as a post-processing step, can achieve good utility for the original clustering objective. Our algorithm matches or improves upon the approximation ratio, space usage, and running time of existing algorithms [Epasto et al., 2026, Dupré la Tour et al., 2024]. A key aspect of our reduction is that it inherits desirable properties of the underlying non-private clustering algorithm, such as consistency [Lattanzi and Vassilvitskii, 2017]--a property not satisfied by previous DP algorithms.
• Abstract（参考訳）: オンラインストリーミング環境における差分プライベート(DP)$k$-meansと$k$-medianクラスタリングについて検討した。 このモデルでは、ポイントが順次到着し、各ステップで、これまでのすべてのポイントに対してクラスタリングの目的を最適化する$k$センターのセットを出力する必要があります。 入力ストリームの半コアセットであるプライベートストリームに(感性)入力ストリームを変換する汎用的なリダクションを与える。 これは、(プライベートでない)オンラインクラスタリングアルゴリズムは、後処理のステップとして実行され、元のクラスタリングの目的に対して優れたユーティリティを達成できることを意味します。 我々のアルゴリズムは既存のアルゴリズム(Epasto et al , 2026, Dupré la Tour et al , 2024]の近似比、空間使用量、実行時間に一致または改善する。 我々の削減の重要な側面は、一貫性(Lattanzi, Vassilvitskii, 2017)のような、基礎となる非プライベートクラスタリングアルゴリズムの望ましい特性を継承することである。

関連論文リスト

• Learning-Augmented Streaming Algorithms for Correlation Clustering [6.0943362338120055]
  相関クラスタリングのためのストリーミングアルゴリズムについて検討する。 完全グラフと一般グラフの両方に関する問題に対して,初めて学習強化されたストリーミングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-10-12T17:04:40Z)
• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  フェデレートされた学習は、参加者のプライバシを備えた機械学習モデルを可能にする。 トレーニングやフィードバックのない問題に対して、差分にプライベートな分散手法は存在しない。 証明可能な収束保証付き分散アルゴリズム$alpha$-$sf NormEC$を導入する。
  論文  参考訳（メタデータ） (2025-02-19T07:10:32Z)
• Dynamic Consistent $k$-Center Clustering with Optimal Recourse [0.6077284832583713]
  我々は、$k$-centerクラスタリング問題において、決定論的定数係数近似を開発することにより、最適リコース境界を許容することを証明する。 当社のインクリメンタルアルゴリズムは,Charikar,Chekuri,Feder,Motwaniによる8ドルの近似アルゴリズムよりも改善されている。
  論文  参考訳（メタデータ） (2024-12-04T11:39:03Z)
• Scalable Algorithms for Individual Preference Stable Clustering [8.01184332330228]
  本稿では,IP安定クラスタリングのための自然局所探索アルゴリズムについて検討する。 このアルゴリズムでは,$O(log n)$-IP安定性が保証され,$n$は入力の点数を表す。
  論文  参考訳（メタデータ） (2024-03-15T14:58:27Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。 当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Individual Preference Stability for Clustering [24.301650646957246]
  本稿では,クラスタリングにおける個別選好(IP)安定性の自然な概念を提案する。 我々の概念は、平均してすべてのデータポイントが、他のどのクラスタのポイントよりも、自身のクラスタのポイントに近いことを要求します。
  論文  参考訳（メタデータ） (2022-07-07T22:01:01Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain [6.824747267214373]
  本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。 従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。 我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
  論文  参考訳（メタデータ） (2021-06-08T23:13:27Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)

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

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