論文の概要: Faster and Space Efficient Indexing for Locality Sensitive Hashing
- arxiv url: http://arxiv.org/abs/2503.06737v1
- Date: Sun, 09 Mar 2025 19:33:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-11 15:45:30.315505
- Title: Faster and Space Efficient Indexing for Locality Sensitive Hashing
- Title（参考訳）: 局所感性ハッシュのための高速かつ空間効率の指標化
- Authors: Bhisham Dev Verma, Rameshwar Pratap,
- Abstract要約: この研究はユークリッド距離(textita.k.a.ELSH)とコサイン類似性(textita.k.a.SRP)の高速かつ空間効率の指標構築アルゴリズムを提案する。
これらのLSHのインデックス構築ステップは、データポイントをハッシュコードに基づいてハッシュテーブルの複数のビンにまとめることに依存している。
$d$次元のデータポイントの$m$次元ハッシュコードを生成するために、これらのLSHはまずデータポイントを$d$次元ランダムガウスベクトルに投影し、それから得られた内部積を離散化する。
- 参考スコア（独自算出の注目度）: 0.06138671548064355
- License:
- Abstract: This work suggests faster and space-efficient index construction algorithms for LSH for Euclidean distance (\textit{a.k.a.}~\ELSH) and cosine similarity (\textit{a.k.a.}~\SRP). The index construction step of these LSHs relies on grouping data points into several bins of hash tables based on their hashcode. To generate an $m$-dimensional hashcode of the $d$-dimensional data point, these LSHs first project the data point onto a $d$-dimensional random Gaussian vector and then discretise the resulting inner product. The time and space complexity of both \ELSH~and \SRP~for computing an $m$-sized hashcode of a $d$-dimensional vector is $O(md)$, which becomes impractical for large values of $m$ and $d$. To overcome this problem, we propose two alternative LSH hashcode generation algorithms both for Euclidean distance and cosine similarity, namely, \CSELSH, \HCSELSH~and \CSSRP, \HCSSRP, respectively. \CSELSH~and \CSSRP~are based on count sketch \cite{count_sketch} and \HCSELSH~and \HCSSRP~utilize higher-order count sketch \cite{shi2019higher}. These proposals significantly reduce the hashcode computation time from $O(md)$ to $O(d)$. Additionally, both \CSELSH~and \CSSRP~reduce the space complexity from $O(md)$ to $O(d)$; ~and \HCSELSH, \HCSSRP~ reduce the space complexity from $O(md)$ to $O(N \sqrt[N]{d})$ respectively, where $N\geq 1$ denotes the size of the input/reshaped tensor. Our proposals are backed by strong mathematical guarantees, and we validate their performance through simulations on various real-world datasets.
- Abstract（参考訳）: この研究は、ユークリッド距離 (\textit{a.k.a.}~\ELSH) とコサイン類似性 (\textit{a.k.a.}~\SRP) に対するLSHの高速かつ空間効率の指標構築アルゴリズムを提案する。
これらのLSHのインデックス構築ステップは、データポイントをハッシュコードに基づいてハッシュテーブルの複数のビンにまとめることに依存している。
$d$次元のデータポイントの$m$次元のハッシュコードを生成するために、これらのLSHはまずデータを$d$次元のランダムガウスベクトルに投影し、その結果の内積を離散化する。
次元ベクトルが$d$の$m$サイズのハッシュコードを計算する場合、時間と空間の複雑さは$O(md)$であり、$m$と$d$の大きな値では非現実的となる。
この問題を解決するために、ユークリッド距離とコサイン類似性、すなわち \CSELSH, \HCSELSH~ \CSSRP, \HCSSRPの2つの代替LSHハッシュコード生成アルゴリズムを提案する。
CSELSH~ and \CSSRP~ are based on count sketch \cite{count_sketch} and \HCSELSH~ and \HCSSRP~utilize higher-order count sketch \cite{shi2019higher}。
これらの提案はハッシュコードの計算時間を$O(md)$から$O(d)$に大幅に短縮する。
さらに、空間複雑性を$O(md)$から$O(d)$; ~and \HCSELSH, \HCSSRP~から$O(md)$から$O(N \sqrt[N]{d})$に還元する。
我々の提案は強力な数学的保証に支えられ、実世界の様々なデータセットのシミュレーションを通してそれらの性能を検証する。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Invertible Bloom Lookup Tables with Less Memory and Randomness [23.724300017513574]
Invertible Bloom Lookup Tables (IBLT) は、セット和解プロトコル、エラー訂正符号、高度な暗号プリミティブの設計に応用されている。
IBLTは同時に空間効率が良く、ランダム性が低い新しい構成を提案する。
k$ の独立ハッシュ関数 $h:U to [Cn]$ for some enough large constant $C$ guarantees with probability $1 - 2-Omega(k)$ that least $n/2$ key will have a unique hash value。
論文 参考訳（メタデータ） (2023-06-13T07:15:02Z) - Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple,
and Practical [1.2183405753834562]
有限集合系 $(X,mathcal S)$ が与えられたとき、2色の $chi:Xto-1,1$ は数学的な S|chi(S)|$ において $max_S として定義される。
我々は、任意の$d>0$と$(X,mathcal S)$に対して、二重シャッター関数 $pi*(k)=O(kd)$ のランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-02T15:59:09Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - 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) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z) - DartMinHash: Fast Sketching for Weighted Sets [0.5584060970507505]
重み付きハッシュは、類似性探索や大規模カーネルマシンに応用した標準的な次元削減手法である。
mathbbR_geq 0d$の重み付き集合を$xとし、期待時間に$k$独立ミンハッシュを計算する単純なアルゴリズムを導入する。
論文 参考訳（メタデータ） (2020-05-23T14:59:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。