論文の概要: Fast Search on Binary Codes by Weighted Hamming Distance

• arxiv url: http://arxiv.org/abs/2009.08591v2
• Date: Tue, 10 Aug 2021 07:36:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-17 03:08:47.687202
• Title: Fast Search on Binary Codes by Weighted Hamming Distance
• Title（参考訳）: 重み付きハミング距離によるバイナリ符号の高速探索
• Authors: Zhenyu Weng, Yuesheng Zhu, Ruixin Liu
• Abstract要約: ハンミング距離を重み付けして最寄りの2進符号を$K$で探索する高速探索アルゴリズムが提案されている。 提案した探索アルゴリズムに基づく高速探索フレームワークは,長いバイナリ符号の問題を解くために設計されている。
• 参考スコア（独自算出の注目度）: 38.50174794945964
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Weighted Hamming distance, as a similarity measure between binary codes and binary queries, provides superior accuracy in search tasks than Hamming distance. However, how to efficiently and accurately find $K$ binary codes that have the smallest weighted Hamming distance to the query remains an open issue. In this paper, a fast search algorithm is proposed to perform the non-exhaustive search for $K$ nearest binary codes by weighted Hamming distance. By using binary codes as direct bucket indices in a hash table, the search algorithm generates a sequence to probe the buckets based on the independence characteristic of the weights for each bit. Furthermore, a fast search framework based on the proposed search algorithm is designed to solve the problem of long binary codes. Specifically, long binary codes are split into substrings and multiple hash tables are built on them. Then, the search algorithm probes the buckets to obtain candidates according to the generated substring indices, and a merging algorithm is proposed to find the nearest binary codes by merging the candidates. Theoretical analysis and experimental results demonstrate that the search algorithm improves the search accuracy compared to other non-exhaustive algorithms and provides orders-of-magnitude faster search than the linear scan baseline.
• Abstract（参考訳）: 重み付きハミング距離は、バイナリコードとバイナリクエリの類似度尺度として、ハミング距離よりも検索タスクにおいて優れた精度を提供する。 しかし、クエリに対して最小の重み付きハミング距離を持つ$k$バイナリコードを効率的に正確に見つけるには、まだ未解決の問題である。 本稿では, 重み付きハミング距離を用いて, 最寄りの2進符号を非排他的に探索する高速探索アルゴリズムを提案する。 ハッシュテーブル内の直接バケットインデックスとしてバイナリコードを使用することで、検索アルゴリズムは、ビット毎のウェイトの独立特性に基づいてバケットを探索するシーケンスを生成する。 さらに,提案アルゴリズムに基づく高速検索フレームワークは,長いバイナリコードの問題を解決するために設計されている。 具体的には、長いバイナリコードはサブストリングに分割され、複数のハッシュテーブルが構築されます。 そして、探索アルゴリズムは、生成された部分文字列インデックスに従ってバケットを探索し、候補をマージして最寄りのバイナリコードを見つけるマージアルゴリズムを提案する。 理論的解析と実験の結果から,検索アルゴリズムは他の非排他的アルゴリズムに比べて検索精度が向上し,線形スキャンベースラインよりも桁違い探索が高速であることが判明した。

関連論文リスト

• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  ストロースト文字列問題(Closest String Problem)は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。 本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。 第二に、解を見つけるためのビーム探索の変種を用いる。この方法は、部分解の期待距離スコアに基づいて、新たに開発された誘導関数を利用する。
  論文  参考訳（メタデータ） (2024-07-17T21:26:27Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。 実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。 本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-13T02:44:05Z)
• Accelerating Code Search with Deep Hashing and Code Classification [64.3543949306799]
  コード検索とは、自然言語クエリに基づいてソースコードコーパスから再利用可能なコードスニペットを検索することである。 深層ハッシュとコード分類を用いたコード検索を高速化する新しい手法CoSHCを提案する。
  論文  参考訳（メタデータ） (2022-03-29T07:05:30Z)
• A Meta-Heuristic Search Algorithm based on Infrasonic Mating Displays in Peafowls [0.0]
  探索アルゴリズムの解空間が増大するにつれて、網羅的探索のような単純な手法は計算コストが高く、信頼性が低いものとなる。 本研究では, 重力探索アルゴリズムとオオカミの交尾行動から着想を得た赤外探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-28T09:04:51Z)
• Searching for a Search Method: Benchmarking Search Algorithms for Generating NLP Adversarial Examples [10.993342896547691]
  自然言語処理(NLP)タスクの逆例を生成するために,複数のブラックボックス探索アルゴリズムの動作について検討した。 検索アルゴリズム,検索空間,検索予算の3つの要素を詳細に分析する。
  論文  参考訳（メタデータ） (2020-09-09T17:04:42Z)
• Faster Person Re-Identification [68.22203008760269]
  本稿では,新しいハッシュコード検索戦略を定式化することによって,高速ReIDのための新しいソリューションを提案する。 より短いコードを使用して、より正確なReIDのいくつかのトップ候補を洗練するために、より広い一致の類似性を粗くランク付けし、より長いコードを使用する。 2つのデータセットに対する実験結果から,提案手法(CtF)は現在のハッシュReID法よりも8%精度が高いだけでなく,5倍高速であることがわかった。
  論文  参考訳（メタデータ） (2020-08-16T03:02:49Z)
• Fast top-K Cosine Similarity Search through XOR-Friendly Binary Quantization on GPUs [1.5828697880068703]
  このアルゴリズムは、浮動小数点数をエンコードするために、新しいXORフレンドリなバイナリ量子化法を用いる。 実験により,我々の量子化法は前処理時間を短縮し,探索手法の探索速度を近辺のアルゴリズムよりもはるかに速くすることがわかった。
  論文  参考訳（メタデータ） (2020-08-05T08:50:21Z)
• A Genetic Algorithm for Obtaining Memory Constrained Near-Perfect Hashing [0.0]
  本稿では,検索時の比較回数の最小化と,総コレクションサイズを最小化することに焦点を当てたハッシュテーブルに基づくアプローチを提案する。 論文は、ほぼ完全なハッシュはバイナリ検索よりも高速であるが、完全なハッシュよりも少ないメモリを使用することを示した。
  論文  参考訳（メタデータ） (2020-07-16T12:57:15Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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