論文の概要: C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with
Circulant Permutations
- arxiv url: http://arxiv.org/abs/2111.09544v1
- Date: Thu, 18 Nov 2021 06:52:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-19 21:30:59.398404
- Title: C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with
Circulant Permutations
- Title（参考訳）: c-oph:循環置換によるone permutation hashing (oph)の精度向上
- Authors: Xiaoyun Li and Ping Li
- Abstract要約: 我々は,C-MinHashの基本的な考え方を取り入れて,一置換ハッシュの精度を向上させることを提案する。
ジャカード類似度の推定分散は、既存の(同定された) OPH 法よりも厳密に小さいことを示すことができる。
- 参考スコア（独自算出の注目度）: 25.356048456005023
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Minwise hashing (MinHash) is a classical method for efficiently estimating
the Jaccrad similarity in massive binary (0/1) data. To generate $K$ hash
values for each data vector, the standard theory of MinHash requires $K$
independent permutations. Interestingly, the recent work on "circulant MinHash"
(C-MinHash) has shown that merely two permutations are needed. The first
permutation breaks the structure of the data and the second permutation is
re-used $K$ time in a circulant manner. Surprisingly, the estimation accuracy
of C-MinHash is proved to be strictly smaller than that of the original
MinHash. The more recent work further demonstrates that practically only one
permutation is needed. Note that C-MinHash is different from the well-known
work on "One Permutation Hashing (OPH)" published in NIPS'12. OPH and its
variants using different "densification" schemes are popular alternatives to
the standard MinHash. The densification step is necessary in order to deal with
empty bins which exist in One Permutation Hashing.
In this paper, we propose to incorporate the essential ideas of C-MinHash to
improve the accuracy of One Permutation Hashing. Basically, we develop a new
densification method for OPH, which achieves the smallest estimation variance
compared to all existing densification schemes for OPH. Our proposed method is
named C-OPH (Circulant OPH). After the initial permutation (which breaks the
existing structure of the data), C-OPH only needs a "shorter" permutation of
length $D/K$ (instead of $D$), where $D$ is the original data dimension and $K$
is the total number of bins in OPH. This short permutation is re-used in $K$
bins in a circulant shifting manner. It can be shown that the estimation
variance of the Jaccard similarity is strictly smaller than that of the
existing (densified) OPH methods.
- Abstract（参考訳）: Minwise hashing(MinHash)は、大規模バイナリ(0/1)データのJaccrad類似性を効率的に推定する古典的な手法である。
データベクトルごとに$K$ハッシュ値を生成するには、MinHashの標準理論は$K$独立置換を必要とする。
興味深いことに、"circulant MinHash"(C-MinHash)に関する最近の研究は、2つの置換しか必要ないことを示している。
第1の置換はデータの構造を破り、第2の置換は循環的に$K$時間に再使用される。
驚いたことに、C-MinHashの推定精度はオリジナルのMinHashよりも厳密に小さいことが証明された。
より最近の研究は、事実上1つの置換しか必要ないことを証明している。
なお、C-MinHash は NIPS'12 で発表された "One Permutation Hashing (OPH)" の有名な作品とは異なる。
OPHとその変種は、標準のMinHashの代替として人気がある。
One Permutation Hashingに存在する空のビンを扱うには、デンシフィケーションステップが必要である。
本稿では,C-MinHashの基本的な考え方を取り入れ,一置換ハッシュの精度を向上させることを提案する。
基本的に,既存のOPHの密度化手法と比較して最小の推定分散を実現する新しいOPHの密度化法を開発した。
提案手法はC-OPH (Circulant OPH) と呼ばれる。
最初の置換(データの既存の構造を壊す)の後、C-OPHは長さ$D/K$($D$の代わりに)の"shorter"の置換しか必要とせず、$D$は元のデータ次元であり、$K$はOPHのビンの総数である。
この短い置換は、循環シフト方式で$K$ビンで再使用される。
ジャカード類似度の推定分散は、既存の(同定された) OPH 法よりも厳密に小さいことを示すことができる。
関連論文リスト
- 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) - 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 Lower Bound of Hash Codes' Performance [122.88252443695492]
本稿では,ハッシュ符号間のクラス間の差分性とクラス内圧縮性が,ハッシュ符号の性能の低い境界を決定することを証明する。
次に、ハッシュコードの後部を推定し、それを制御することにより、上記の目的を完全に活用する代理モデルを提案し、低バイアス最適化を実現する。
一連のハッシュモデルをテストすることで、平均精度が最大で26.5%、精度が最大で20.5%向上した。
論文 参考訳（メタデータ） (2022-10-12T03:30:56Z) - Learning to Hash Naturally Sorts [84.90210592082829]
そこで我々はNaturely-Sorted Hashing (NSH)を導入し,最終結果のソートによる深層ハッシュモデルのトレーニングを行った。
NSHはサンプルのハッシュコードのハミング距離をソートし、それに従って自己教師付きトレーニングのための潜伏した表現を収集する。
Sorted Noise-Contrastive Estimation (SortedNCE) の新たな損失について述べる。
論文 参考訳（メタデータ） (2022-01-31T16:19:02Z) - C-MinHash: Practically Reducing Two Permutations to Just One [25.356048456005023]
従来のミンワイズハッシュ (MinHash) では、大量のバイナリ (0/1) データで Jaccard の類似性を推定するために、$K$ の独立した置換を適用する必要がある。
C-MinHashに関する最近の研究は、2つの置換しか必要ないことを示している。
1つの単一の置換は、データの構造を壊す最初の前処理ステップと、K$ハッシュを生成する循環ハッシュステップの両方に使用される。
論文 参考訳（メタデータ） (2021-09-10T00:08:47Z) - 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) - Procrustean Orthogonal Sparse Hashing [3.302605292858623]
昆虫の嗅覚は, スパースハッシュと構造的に, 機能的に類似していることが示されている。
本稿ではこれらの知見を統一する新しい方法であるPOSH(Procrustean Orthogonal Sparse Hashing)を提案する。
本稿では,これらの欠陥に対処する2つの新しい手法,Binary OSLとSphericalHashを提案する。
論文 参考訳（メタデータ） (2020-06-08T18:09:33Z) - Reinforcing Short-Length Hashing [61.75883795807109]
既存の手法は、非常に短いハッシュコードを用いた検索性能が劣っている。
本研究では, 短寿命ハッシュ(RSLH)を改良する新しい手法を提案する。
本稿では,ハッシュ表現とセマンティックラベルの相互再構成を行い,セマンティック情報を保存する。
3つの大規模画像ベンチマークの実験は、様々な短いハッシュシナリオ下でのRSLHの優れた性能を示す。
論文 参考訳（メタデータ） (2020-04-24T02:23:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。