論文の概要: Fast Locality Sensitive Hashing with Theoretical Guarantee

• arxiv url: http://arxiv.org/abs/2309.15479v1
• Date: Wed, 27 Sep 2023 08:21:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-28 14:44:14.036572
• Title: Fast Locality Sensitive Hashing with Theoretical Guarantee
• Title（参考訳）: 理論的保証による高速局所感性ハッシュ
• Authors: Zongyuan Tan, Hongya Wang, Bo Xu, Minjie Luo and Ming Du
• Abstract要約: 局所性に敏感なハッシュ(LSH)は、多くの機械学習タスクで広く使われている効果的なランダム化手法である。 本稿では,l2 ノルムの下で,FastLSH という名前の簡易かつ効率的な LSH スキームを設計する。 ランダムサンプリングとランダムプロジェクションを組み合わせることで、FastLSHは時間複雑性を O(n) から O(m) (mn) に還元する。 実験結果から,FastLSHは回答の品質,空間占有,クエリ効率の面で,最先端技術と同等であることがわかった。
• 参考スコア（独自算出の注目度）: 5.635783105833339
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Locality-sensitive hashing (LSH) is an effective randomized technique widely used in many machine learning tasks. The cost of hashing is proportional to data dimensions, and thus often the performance bottleneck when dimensionality is high and the number of hash functions involved is large. Surprisingly, however, little work has been done to improve the efficiency of LSH computation. In this paper, we design a simple yet efficient LSH scheme, named FastLSH, under l2 norm. By combining random sampling and random projection, FastLSH reduces the time complexity from O(n) to O(m) (m<n), where n is the data dimensionality and m is the number of sampled dimensions. Moreover, FastLSH has provable LSH property, which distinguishes it from the non-LSH fast sketches. We conduct comprehensive experiments over a collection of real and synthetic datasets for the nearest neighbor search task. Experimental results demonstrate that FastLSH is on par with the state-of-the-arts in terms of answer quality, space occupation and query efficiency, while enjoying up to 80x speedup in hash function evaluation. We believe that FastLSH is a promising alternative to the classic LSH scheme.
• Abstract（参考訳）: 局所性センシティブハッシュ(lsh)は、多くの機械学習タスクで広く使われている効果的なランダム化技術である。 ハッシュのコストはデータ次元に比例するので、次元が高く、関連するハッシュ関数の数が大きい場合のパフォーマンスボトルネックがしばしば発生する。 しかし、驚くべきことに、LSH計算の効率を改善するための作業はほとんど行われていない。 本稿では,l2 ノルムの下で,FastLSH という名前の簡易かつ効率的な LSH スキームを設計する。 ランダムサンプリングとランダムプロジェクションを組み合わせることで、FastLSHはOから時間複雑さを減らす (n)→O (m) (m<n) ここで n はデータ次元、m はサンプル次元の数である。 さらに、FastLSHは証明可能なLSHプロパティを持ち、非LSHの高速スケッチと区別する。 近隣の探索課題に対する実・合成データセットの集合に関する総合的な実験を行う。 実験結果から,FastLSHは応答品質,空間占有率,クエリ効率の点で最先端技術と同等であり,ハッシュ関数の評価では最大80倍の高速化が期待できることがわかった。 我々は、FastLSHが古典的なLSH方式に代わる有望な選択肢であると考えている。

関連論文リスト

• DeepLSH: Deep Locality-Sensitive Hash Learning for Fast and Efficient Near-Duplicate Crash Report Detection [0.29998889086656577]
  リアルタイムストリーミングバグ収集では、システムはすぐに質問に答える必要がある: 新しいバグと最もよく似たバグは何か? LSHは、クラッシュバケットの文献では考慮されていない。 本稿では、局所性感度特性を完璧に近似した、元の損失関数を持つシームズアーキテクチャであるDeepLSHを紹介する。
  論文  参考訳（メタデータ） (2023-10-10T15:26:27Z)
• HUSP-SP: Faster Utility Mining on Sequence Data [48.0426095077918]
  高実用性シーケンシャルパターンマイニング (HUSPM) が重要視されている。 シークエンスプロジェクション(seqPro)と呼ばれるコンパクトな構造を設計し、シークエンスプロ構造(HUSP-SP)を用いた効率的なアルゴリズムを提案する。 HUSP-SPは, 実行時間, メモリ使用量, 検索空間のプルーニング効率, スケーラビリティにおいて, 最先端のアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2022-12-29T10:56:17Z)
• Experimental Analysis of Machine Learning Techniques for Finding Search Radius in Locality Sensitive Hashing [0.9137554315375919]
  局所感性ハッシュ (Locality Sensitive Hashing, LSH) は、高次元空間の近接探索技術として最も一般的なものの一つである。 機械学習を利用するために、半径最適化局所感性ハッシュ(roLSH)と呼ばれる改良されたLSHベースのインデックス構造が提案されている。
  論文  参考訳（メタデータ） (2022-11-16T18:19:10Z)
• A Lower Bound of Hash Codes' Performance [122.88252443695492]
  本稿では,ハッシュ符号間のクラス間の差分性とクラス内圧縮性が,ハッシュ符号の性能の低い境界を決定することを証明する。 次に、ハッシュコードの後部を推定し、それを制御することにより、上記の目的を完全に活用する代理モデルを提案し、低バイアス最適化を実現する。 一連のハッシュモデルをテストすることで、平均精度が最大で26.5%、精度が最大で20.5%向上した。
  論文  参考訳（メタデータ） (2022-10-12T03:30:56Z)
• NumS: Scalable Array Programming for the Cloud [82.827921577004]
  タスクベース分散システム上でNumPyのような表現を最適化する配列プログラミングライブラリであるNumSを提案する。 これはLoad Simulated Hierarchical Scheduling (LSHS)と呼ばれる新しいスケジューラによって実現される。 LSHSは、ネットワーク負荷を2倍減らし、メモリを4倍減らし、ロジスティック回帰問題において実行時間を10倍減らし、Rayの性能を向上させる。
  論文  参考訳（メタデータ） (2022-06-28T20:13:40Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
  本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。 我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
  論文  参考訳（メタデータ） (2021-05-18T05:23:53Z)
• Unsupervised Multi-Index Semantic Hashing [23.169142004594434]
  マルチインデックスハッシュに最適化することで,効率的かつ高効率なハッシュコードを学習する教師なしハッシュモデルを提案する。 文書類似度検索のタスクにおいて、MISHと最先端のセマンティックハッシュベースラインを実験的に比較する。 マルチインデックスハッシュは、線形スキャンと比較してベースラインの効率も向上しますが、MISHよりも33%遅くなっています。
  論文  参考訳（メタデータ） (2021-03-26T13:33:48Z)
• Reinforcing Short-Length Hashing [61.75883795807109]
  既存の手法は、非常に短いハッシュコードを用いた検索性能が劣っている。 本研究では, 短寿命ハッシュ(RSLH)を改良する新しい手法を提案する。 本稿では,ハッシュ表現とセマンティックラベルの相互再構成を行い,セマンティック情報を保存する。 3つの大規模画像ベンチマークの実験は、様々な短いハッシュシナリオ下でのRSLHの優れた性能を示す。
  論文  参考訳（メタデータ） (2020-04-24T02:23:52Z)
• Image Hashing by Minimizing Discrete Component-wise Wasserstein Distance [12.968141477410597]
  競合するオートエンコーダは、バランスよく高品質なハッシュコードを生成する堅牢で局所性を保存するハッシュ関数を暗黙的に学習できることが示されている。 既存の逆ハッシュ法は、大規模な画像検索に非効率である。 本稿では,サンプル要求と計算コストを大幅に低減した,新しい対向型オートエンコーダハッシュ手法を提案する。
  論文  参考訳（メタデータ） (2020-02-29T00:22:53Z)

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

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