論文の概要: C-MinHash: Practically Reducing Two Permutations to Just One
- arxiv url: http://arxiv.org/abs/2109.04595v1
- Date: Fri, 10 Sep 2021 00:08:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-14 01:10:15.635332
- Title: C-MinHash: Practically Reducing Two Permutations to Just One
- Title（参考訳）: C-MinHash: 2つの命令を1つに事実上削減する
- Authors: Xiaoyun Li and Ping Li
- Abstract要約: 従来のミンワイズハッシュ (MinHash) では、大量のバイナリ (0/1) データで Jaccard の類似性を推定するために、$K$ の独立した置換を適用する必要がある。
C-MinHashに関する最近の研究は、2つの置換しか必要ないことを示している。
1つの単一の置換は、データの構造を壊す最初の前処理ステップと、K$ハッシュを生成する循環ハッシュステップの両方に使用される。
- 参考スコア（独自算出の注目度）: 25.356048456005023
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Traditional minwise hashing (MinHash) requires applying $K$ independent
permutations to estimate the Jaccard similarity in massive binary (0/1) data,
where $K$ can be (e.g.,) 1024 or even larger, depending on applications. The
recent work on C-MinHash (Li and Li, 2021) has shown, with rigorous proofs,
that only two permutations are needed. An initial permutation is applied to
break whatever structures which might exist in the data, and a second
permutation is re-used $K$ times to produce $K$ hashes, via a circulant
shifting fashion. (Li and Li, 2021) has proved that, perhaps surprisingly, even
though the $K$ hashes are correlated, the estimation variance is strictly
smaller than the variance of the traditional MinHash.
It has been demonstrated in (Li and Li, 2021) that the initial permutation in
C-MinHash is indeed necessary. For the ease of theoretical analysis, they have
used two independent permutations. In this paper, we show that one can actually
simply use one permutation. That is, one single permutation is used for both
the initial pre-processing step to break the structures in the data and the
circulant hashing step to generate $K$ hashes. Although the theoretical
analysis becomes very complicated, we are able to explicitly write down the
expression for the expectation of the estimator. The new estimator is no longer
unbiased but the bias is extremely small and has essentially no impact on the
estimation accuracy (mean square errors). An extensive set of experiments are
provided to verify our claim for using just one permutation.
- Abstract（参考訳）: 従来のミンワイズハッシュ (MinHash) では、アプリケーションによっては1024ドル以上の大容量バイナリ (0/1) のデータで Jaccard の類似性を推定するために、$K$ の独立置換を適用する必要がある。
C-MinHash (Li and Li, 2021) に関する最近の研究は、厳密な証明により、2つの置換しか必要ないことを示した。
最初の置換は、データに存在する可能性のある構造を壊すために適用され、第2の置換は、循環シフト方式で$K$ハッシュを生成するために$K$倍に再使用される。
(Li, Li, 2021)は、おそらく驚くべきことに、K$ハッシュが相関しているにもかかわらず、推定分散が従来のMinHashの分散よりも厳密に小さいことを証明している。
Li と Li, 2021) では、C-MinHash における初期置換が本当に必要であることが示されている。
理論解析の容易さのために、2つの独立した置換を用いた。
本稿では,一つの置換のみを実際に使用できることを示す。
つまり、データの構造を壊す最初の前処理ステップと、$k$ハッシュを生成する循環ハッシュステップの両方に、1つの置換が使用される。
理論的解析は非常に複雑になるが、推定子の期待値の表現を明示的に書き留めることができる。
新しい推定器はもはや偏りがないが、バイアスは極端に小さく、推定精度(正方形誤差)には本質的に影響しない。
1つの置換だけを使用するという我々の主張を検証するために、広範な実験セットが提供される。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Pb-Hash: Partitioned b-bit Hashing [21.607059258448594]
我々は、$B$ビットを$m$チャンク、例えば$btimes m =B$に分割することでハッシュを再使用することを提案する。
我々の理論的分析により、ハッシュ値を$m$チャンクに分割することで、精度が低下することが明らかとなった。
一部のリージョンでは、Pb-Hashは4.9ドルよりもずっと大きい$m$でもうまく機能している。
論文 参考訳（メタデータ） (2023-06-28T06:05:47Z) - Differentially Private One Permutation Hashing and Bin-wise Consistent
Weighted Sampling [37.6593006747285]
Minwise hashing (MinHash) は、大規模な検索および学習アプリケーションで広く使われている標準アルゴリズムである。
1つの置換ハッシュ(OPH)は、データベクトルを$K$ binに分割し、各bin内でハッシュ値を生成するMinHashの効率的な代替手段である。
我々は, DP-OPH-fix, DP-OPH-re, DP-OPH-randの3つの変種を用いたDP-OPHフレームワークを提案する。
論文 参考訳（メタデータ） (2023-06-13T10:38:12Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - A Permutation-Free Kernel Independence Test [36.50719125230106]
非パラメトリック独立試験では、i.d. data $(X_i,Y_i)_i=1n$, where $X in MathcalX, Y in MathcalY$ is in any general space。
カーネルHilbert-Schmidt Independence Criterion (HSIC) や Distance Covariance (dCov) のような現代のテスト統計は、基礎となるU統計の縮退により、難解なnull分布を持つ。
本稿では,HSICの簡易かつ非自明な修正について述べる。
論文 参考訳（メタデータ） (2022-12-18T15:28:16Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with
Circulant Permutations [25.356048456005023]
我々は,C-MinHashの基本的な考え方を取り入れて,一置換ハッシュの精度を向上させることを提案する。
ジャカード類似度の推定分散は、既存の(同定された) OPH 法よりも厳密に小さいことを示すことができる。
論文 参考訳（メタデータ） (2021-11-18T06:52:15Z) - C-MinHash: Rigorously Reducing $K$ Permutations to Two [25.356048456005023]
MinHash (Minwise hashing) は、大量のバイナリ (0/1) データにおける Jaccard (resemblance) の類似性を近似するために、ランダムハッシュを生成するための重要かつ実用的なアルゴリズムである。
我々は、bf Circulant MinHash (C-MinHash)を提案する。
論文 参考訳（メタデータ） (2021-09-07T21:06:33Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。