論文の概要: MaxSketch: Robust Distinct Counting in Streams via Random Projections
- arxiv url: http://arxiv.org/abs/2605.15571v1
- Date: Fri, 15 May 2026 03:29:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-18 21:22:26.159091
- Title: MaxSketch: Robust Distinct Counting in Streams via Random Projections
- Title（参考訳）: MaxSketch: ランダム投影によるストリーム中のロバストな個別カウント
- Authors: Nikos Tsikouras, Constantine Caramanis, Christos Tzamos,
- Abstract要約: データストリーム内の異なる要素数を推定することは、繰り返し要素が同一であるときによく理解される。
一般距離空間におけるロバストな別個の数え上げに関する最近の研究は、$widetilde(sqrtn)$ memory を達成する。
学習表現に共通する幾何学的構造の下では,メモリ保証の大幅な改善が可能であることを示す。
- 参考スコア（独自算出の注目度）: 36.0349574328815
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Estimating the number of distinct elements in a data stream is well understood when repeated elements are identical. In modern settings, however, observations are high-dimensional and noisy, so repeated instances of the same object are only approximately similar -- for example, different images of the same individual may vary significantly at the pixel level. Classical sketches such as HyperLogLog rely on consistent hash values for identical elements and break down in this regime. Recent work on robust distinct counting in general metric spaces achieves $\widetildeΘ(\sqrt{n})$ memory, which is tight in the worst case. We show that substantially improved memory guarantees are possible under geometric structure common in learned representations. We introduce MaxSketch, a simple max-linear sketch built from random Gaussian projections, and prove that it succeeds in estimating the number of distinct latent objects. Concretely, we show that under this assumption $m = \widetilde{O} (\log n / \varepsilon^2)$ random projections (and hence $\widetilde{O} (\log n/\varepsilon^2)$ memory) suffice to recover the true distinct count within a $(1+\varepsilon)$ factor. Experiments on image streams confirm that MaxSketch accurately estimates distinct counts and generalizes beyond the training regime. Our results bridge classical streaming algorithms and modern representation learning, showing how geometric structure can fundamentally reduce the complexity of distinct counting.
- Abstract（参考訳）: データストリーム内の異なる要素数を推定することは、繰り返し要素が同一であるときによく理解される。
しかし、現代の設定では、観測は高次元でノイズが多いため、同じ物体の繰り返しの例は、ほぼ同様である(例えば、同じ個体の異なる画像はピクセルレベルで大きく異なる)。
HyperLogLogのような古典的なスケッチは、同じ要素に対して一貫したハッシュ値に依存しており、この仕組みで分解される。
一般計量空間におけるロバストな別個の数え上げに関する最近の研究は、$\widetilde'(\sqrt{n})$ memory を達成するが、これは最悪の場合、厳密である。
学習表現に共通する幾何学的構造の下では,メモリ保証の大幅な改善が可能であることを示す。
ランダムなガウス射影から構築された単純な最大線形スケッチであるMaxSketchを導入し、異なる潜在オブジェクトの数を推定することに成功した。
具体的には、この仮定の下では、$m = \widetilde{O} (\log n / \varepsilon^2)$ ランダム射影(従って$\widetilde{O} (\log n/\varepsilon^2)$ メモリ)は、$(1+\varepsilon)$ で真に異なるカウントを回復するのに十分であることを示す。
画像ストリームの実験では、MaxSketchが個別のカウントを正確に推定し、トレーニング体制を超えて一般化していることを確認した。
この結果は,従来のストリーミングアルゴリズムと現代的な表現学習を橋渡しし,幾何学構造が異なるカウントの複雑さを根本的に軽減することを示す。
関連論文リスト
- The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
この研究において、ラベルは(ガウス)$d$-次元入力にのみ依存し、低次元$r = O_d(1)$部分空間への射影を通して得られる。
生成的跳躍指数 $kstar$, [Damian et al.'24] から生成的指数の自然拡張をマルチインデックス設定に導入する。
論文 参考訳（メタデータ） (2025-06-05T18:34:56Z) - Quantum search by continuous-time quantum walk on t-designs [0.0]
本研究は、連続時間量子ウォークを用いて、複数のマークされた要素を持つ$t$-designs上の量子検索アルゴリズムの時間的複雑さについて検討する。
ランダムウォークに基づく探索アルゴリズムと比較して,成功に導かれる二部グラフのサブセットを同定する。
論文 参考訳（メタデータ） (2023-10-22T00:37:52Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Algorithmic Gaussianization through Sketching: Converting Data into
Sub-gaussian Random Designs [22.925108493465363]
平均化によるデータ分布のガウシアン化のためのアルゴリズムフレームワークを提供する。
我々は、ガウス以下のランダムな設計とほとんど区別できないデータスケッチを効率的に構築できることを示す。
論文 参考訳（メタデータ） (2022-06-21T12:16:45Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Recurrently Predicting Hypergraphs [30.092688729343678]
問題は、$n$要素の集合に対して$mathcalO(2n)$でスケーリング可能なマルチウェイ関係(ハイパーエッジ)の数から生じる。
そこで本研究では,提案手法の初期推定を反復的に精算することにより,入射行列を予測する再帰型ハイパーグラフニューラルネットワークを提案する。
論文 参考訳（メタデータ） (2021-06-26T01:12:41Z) - Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。
複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。
これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
論文 参考訳（メタデータ） (2021-03-25T14:35:07Z) - Functions with average smoothness: structure, algorithms, and learning [12.362670630646804]
各点における局所勾配を定義し、これらの値の平均として関数複雑性を測る。
平均は最大よりも劇的に小さくなるので、この複雑性測度はよりシャープな一般化境界が得られる。
私たちは定義した関数クラスにおいて驚くほどリッチで解析的な構造を発見します。
論文 参考訳（メタデータ） (2020-07-13T10:06:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。