論文の概要: LSI: A Learned Secondary Index Structure
- arxiv url: http://arxiv.org/abs/2205.05769v1
- Date: Wed, 11 May 2022 20:49:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-13 14:18:48.847986
- Title: LSI: A Learned Secondary Index Structure
- Title(参考訳): LSI: 学習された二次インデックス構造
- Authors: Andreas Kipf, Dominik Horn, Pascal Pfeil, Ryan Marcus, Tim Kraska
- Abstract要約: 本研究では,未分類データのインデックス化に学習指標を使用する最初の試みであるLearnered secondary Index(LSI)を紹介する。
LSIは最先端のセカンダリインデックスに匹敵するルックアップ性能を実現し,空間効率を最大6倍に向上することを示す。
- 参考スコア(独自算出の注目度): 24.324528705706104
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learned index structures have been shown to achieve favorable lookup
performance and space consumption compared to their traditional counterparts
such as B-trees. However, most learned index studies have focused on the
primary indexing setting, where the base data is sorted. In this work, we
investigate whether learned indexes sustain their advantage in the secondary
indexing setting. We introduce Learned Secondary Index (LSI), a first attempt
to use learned indexes for indexing unsorted data. LSI works by building a
learned index over a permutation vector, which allows binary search to
performed on the unsorted base data using random access. We additionally
augment LSI with a fingerprint vector to accelerate equality lookups. We show
that LSI achieves comparable lookup performance to state-of-the-art secondary
indexes while being up to 6x more space efficient.
- Abstract(参考訳): 学習された索引構造は、B木などの伝統的な指標と比較して、良好なルックアップ性能と空間消費を実現することが示されている。
しかし、ほとんどの学習されたインデックス研究は、ベースデータをソートするプライマリインデックス設定に焦点を当てている。
本研究では,学習指標がセカンダリインデックス設定において優位性を維持するかどうかを検討する。
本研究では,未分類データのインデックス化に学習指標を使用する最初の試みであるLearnered secondary Index(LSI)を紹介する。
LSIは、学習したインデックスを置換ベクトル上に構築することで、ランダムアクセスを使用して、未分類のベースデータ上でバイナリ検索を行うことができる。
さらに,lsiを指紋ベクターで拡張し,等式検索を高速化する。
LSIは最先端のセカンダリインデックスに匹敵するルックアップ性能を実現し,空間効率を最大6倍に向上することを示す。
関連論文リスト
- Autoregressive Search Engines: Generating Substrings as Document
Identifiers [53.0729058170278]
自動回帰言語モデルは、回答を生成するデファクト標準として現れています。
これまでの研究は、探索空間を階層構造に分割する方法を探究してきた。
本研究では,検索空間の任意の構造を強制しない代替として,経路内のすべてのngramを識別子として使用することを提案する。
論文 参考訳(メタデータ) (2022-04-22T10:45:01Z) - A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
LIMSは、学習したインデックスを構築するために、データクラスタリングとピボットベースのデータ変換技術を使用することが提案されている。
機械学習モデルはディスク上の各データレコードの位置を近似するために開発された。
実世界のデータセットと合成データセットに関する大規模な実験は、従来の指標と比較してLIMSの優位性を示している。
論文 参考訳(メタデータ) (2022-04-21T11:24:55Z) - Transformer Memory as a Differentiable Search Index [102.41278496436948]
本稿では,文字列クエリを関連するドシデントに直接マップするテキストからテキストモデルを学ぶ新しいパラダイムであるdiffariable Search Index (DSI)を紹介する。
文書とその識別子の表現方法、訓練手順のバリエーション、モデルとコーパスサイズ間の相互作用について検討する。
論文 参考訳(メタデータ) (2022-02-14T19:12:43Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳(メタデータ) (2022-01-25T00:10:03Z) - Standard Vs Uniform Binary Search and Their Variants in Learned Static
Indexing: The Case of the Searching on Sorted Data Benchmarking Software
Platform [0.0]
学習者にとって、bf SOSDソフトウェアに関して、標準ルーチンの使用はUniformよりも優れていることを示す。
実験の結果,一様二項探索とk-ary Searchは学習空間の節約に有用であることが示唆された。
論文 参考訳(メタデータ) (2022-01-05T11:46:16Z) - Micro-architectural Analysis of a Learned Index [0.0]
ALEXはツリーベースのインメモリインデックス構造であり、機械学習モデルの階層構造で構成されている。
その結果、ALEXはストールを少なくし、異なるワークロードにまたがるインストラクションあたりのサイクル値が低いことがわかった。
一方、ALEXのアウト・オブ・バウンド・インサートを扱うのに必要な命令の量は、リクエスト毎の命令を著しく増加させる(10X)。
論文 参考訳(メタデータ) (2021-09-17T12:13:06Z) - Learning to Hash Robustly, with Guarantees [79.68057056103014]
本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。
理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。
我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
論文 参考訳(メタデータ) (2021-08-11T20:21:30Z) - IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。
クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。
我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文 参考訳(メタデータ) (2021-03-17T23:13:25Z) - A Pluggable Learned Index Method via Sampling and Gap Insertion [48.900186573181735]
データベースインデックスは、データ検索を促進し、現実世界のシステムにおける幅広いアプリケーションに役立つ。
近年,隠れて有用なデータ分布を学習するために,learning indexという新しいインデックスが提案されている。
学習指標の学習効率と学習効率を高めるための2つの一般的なテクニックとプラグイン可能なテクニックを研究します。
論文 参考訳(メタデータ) (2021-01-04T07:17:23Z) - Learned Indexes for a Google-scale Disk-based Database [23.93643265060042]
学習したインデックスが分散ディスクベースのデータベースシステムにどのように統合できるかを示す: GoogleのBigtable。
その結果,学習インデックスの統合により,bigtableの読み取りレイテンシとスループットが大幅に向上することがわかった。
論文 参考訳(メタデータ) (2020-12-23T05:56:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。