論文の概要: IDentity with Locality: An ideal hash for gene sequence search

• arxiv url: http://arxiv.org/abs/2406.14901v1
• Date: Fri, 21 Jun 2024 06:47:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-10 21:11:13.696804
• Title: IDentity with Locality: An ideal hash for gene sequence search
• Title（参考訳）: IDentity with Locality: 遺伝子シークエンス検索のための理想的なハッシュ
• Authors: Aditya Desai, Gaurav Gupta, Tianyi Zhang, Anshumali Shrivastava,
• Abstract要約: 大部分の遺伝子検索システムは、ブルームフィルタ(BF)のようなハッシュベースのデータ構造を使っている。 本稿では,IDL(Identity with Locality)ハッシュファミリーと呼ばれる新しいハッシュ関数を提案する。
• 参考スコア（独自算出の注目度）: 34.574424989422674
• License:
• Abstract: Gene sequence search is a fundamental operation in computational genomics. Due to the petabyte scale of genome archives, most gene search systems now use hashing-based data structures such as Bloom Filters (BF). The state-of-the-art systems such as Compact bit-slicing signature index (COBS) and Repeated And Merged Bloom filters (RAMBO) use BF with Random Hash (RH) functions for gene representation and identification. The standard recipe is to cast the gene search problem as a sequence of membership problems testing if each subsequent gene substring (called kmer) of Q is present in the set of kmers of the entire gene database D. We observe that RH functions, which are crucial to the memory and the computational advantage of BF, are also detrimental to the system performance of gene-search systems. While subsequent kmers being queried are likely very similar, RH, oblivious to any similarity, uniformly distributes the kmers to different parts of potentially large BF, thus triggering excessive cache misses and causing system slowdown. We propose a novel hash function called the Identity with Locality (IDL) hash family, which co-locates the keys close in input space without causing collisions. This approach ensures both cache locality and key preservation. IDL functions can be a drop-in replacement for RH functions and help improve the performance of information retrieval systems. We give a simple but practical construction of IDL function families and show that replacing the RH with IDL functions reduces cache misses by a factor of 5x, thus improving query and indexing times of SOTA methods such as COBS and RAMBO by factors up to 2x without compromising their quality. We also provide a theoretical analysis of the false positive rate of BF with IDL functions. Our hash function is the first study that bridges Locality Sensitive Hash (LSH) and RH to obtain cache efficiency.
• Abstract（参考訳）: 遺伝子配列探索は、計算ゲノミクスの基本的な操作である。 ゲノムアーカイブのペタバイト規模のため、ほとんどの遺伝子検索システムはブルームフィルタ(BF)のようなハッシュベースのデータ構造を使用している。 Compact bit-slicing signature index (COBS) や Repeated And Merged Bloom Filters (RAMBO) などの最先端システムは、遺伝子表現と識別にRandom Hash (RH) 機能付きBFを使用する。 本手法は,Q の各遺伝子サブストリング (kmer と呼ばれる) が全遺伝子データベース D のkmers の集合に存在する場合の会員問題の系列として,遺伝子探索問題をキャストすることである。 その後のkmersのクエリはおそらく非常に似ているが、RHはどんな類似性も無視し、kmersを潜在的に大きなBFの異なる部分に均一に分散させ、過剰なキャッシュミスを引き起こし、システムの減速を引き起こす。 本稿では,IDL(Identity with Locality)ハッシュファミリーと呼ばれる新しいハッシュ関数を提案する。 このアプローチはキャッシュのローカリティとキー保存の両方を保証する。 IDL関数は、RH関数のドロップイン置換であり、情報検索システムの性能向上に役立つ。 IDL関数ファミリの単純かつ実用的な構築を行い、RHをIDL関数に置き換えることでキャッシュミスを5倍減らし、COBSやRAMBOなどのSOTAメソッドのクエリとインデックス化時間を2倍に改善できることを示す。 また,IDL関数を用いたBFの偽陽性率の理論的解析を行った。 我々のハッシュ機能は、キャッシュ効率を得るためにLocality Sensitive Hash(LSH)とRHを橋渡しする最初の研究である。

関連論文リスト

• Prototypical Hash Encoding for On-the-Fly Fine-Grained Category Discovery [65.16724941038052]
  カテゴリ対応プロトタイプ生成(CPG)とディスクリミカテゴリ5.3%(DCE)が提案されている。 CPGは、各カテゴリを複数のプロトタイプで表現することで、カテゴリ内の多様性を完全にキャプチャすることを可能にする。 DCEは生成されたカテゴリプロトタイプのガイダンスによってハッシュコードの識別能力を向上する。
  論文  参考訳（メタデータ） (2024-10-24T23:51:40Z)
• Sparse-Inductive Generative Adversarial Hashing for Nearest Neighbor Search [8.020530603813416]
  本稿では,Sparsity-induced Generative Adversarial Hashing (SiGAH)と呼ばれる新しい教師なしハッシュ法を提案する。 SiGAHは、大規模な高次元特徴をバイナリコードにエンコードする。 Tiny100K、GIST1M、Deep1M、MNISTの4つのベンチマーク実験の結果、提案されたSiGAHは最先端のアプローチよりも優れた性能を示している。
  論文  参考訳（メタデータ） (2023-06-12T08:07:23Z)
• Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
  高速に統一された関数型ハッシュを用いることで,大きな効率向上が得られることを示す。 私たちのハッシュは"機能的"であり、表現やコードが異なる場合でも同等の候補を識別します。 ニューラルアーキテクチャ検索やアルゴリズム発見など、複数のAutoMLドメインで劇的な改善がなされている。
  論文  参考訳（メタデータ） (2023-02-10T18:50:37Z)
• Asymmetric Transfer Hashing with Adaptive Bipartite Graph Learning [95.54688542786863]
  既存のハッシュ法では、クエリと検索サンプルは同じドメイン内の同質な特徴空間にあると仮定する。 教師なし/半教師付き/教師付き実現のための非対称トランスファーハッシュ(ATH)フレームワークを提案する。 非対称ハッシュ関数と二部グラフを共同最適化することにより、知識伝達が達成できるだけでなく、特徴アライメントによる情報損失も回避できる。
  論文  参考訳（メタデータ） (2022-06-25T08:24:34Z)
• A Genetic Algorithm for Obtaining Memory Constrained Near-Perfect Hashing [0.0]
  本稿では,検索時の比較回数の最小化と,総コレクションサイズを最小化することに焦点を当てたハッシュテーブルに基づくアプローチを提案する。 論文は、ほぼ完全なハッシュはバイナリ検索よりも高速であるが、完全なハッシュよりも少ないメモリを使用することを示した。
  論文  参考訳（メタデータ） (2020-07-16T12:57:15Z)
• Pairwise Supervised Hashing with Bernoulli Variational Auto-Encoder and Self-Control Gradient Estimator [62.26981903551382]
  バイナリ潜在変数を持つ変分自動エンコーダ(VAE)は、文書検索の精度の観点から最先端のパフォーマンスを提供する。 本稿では、クラス内類似度とクラス間類似度に報いるために、個別潜伏型VAEを用いたペアワイズ損失関数を提案する。 この新しいセマンティックハッシュフレームワークは、最先端技術よりも優れたパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2020-05-21T06:11:33Z)
• Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice [36.8421113576893]
  n 変数上の CNF 式 F が与えられたとき、モデルカウントや #SAT の問題は F の満足な割り当ての数を計算することである。 近年,効率的なアルゴリズム技術開発への取り組みが急増している。
  論文  参考訳（メタデータ） (2020-04-30T11:17:26Z)
• Reinforcing Short-Length Hashing [61.75883795807109]
  既存の手法は、非常に短いハッシュコードを用いた検索性能が劣っている。 本研究では, 短寿命ハッシュ(RSLH)を改良する新しい手法を提案する。 本稿では,ハッシュ表現とセマンティックラベルの相互再構成を行い,セマンティック情報を保存する。 3つの大規模画像ベンチマークの実験は、様々な短いハッシュシナリオ下でのRSLHの優れた性能を示す。
  論文  参考訳（メタデータ） (2020-04-24T02:23:52Z)

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

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