論文の概要: Micro-architectural Analysis of a Learned Index

• arxiv url: http://arxiv.org/abs/2109.08495v1
• Date: Fri, 17 Sep 2021 12:13:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-20 18:37:10.123159
• Title: Micro-architectural Analysis of a Learned Index
• Title（参考訳）: 学習指標のマイクロアーキテクチャ解析
• Authors: Mikkel M{\o}ller Andersen, P{\i}nar T\"oz\"un
• Abstract要約: ALEXはツリーベースのインメモリインデックス構造であり、機械学習モデルの階層構造で構成されている。 その結果、ALEXはストールを少なくし、異なるワークロードにまたがるインストラクションあたりのサイクル値が低いことがわかった。 一方、ALEXのアウト・オブ・バウンド・インサートを扱うのに必要な命令の量は、リクエスト毎の命令を著しく増加させる(10X)。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Since the publication of The Case for Learned Index Structures in 2018, there has been a rise in research that focuses on learned indexes for different domains and with different functionalities. While the effectiveness of learned indexes as an alternative to traditional index structures such as B+Trees have already been demonstrated by several studies, previous work tend to focus on higher-level performance metrics such as throughput and index size. In this paper, our goal is to dig deeper and investigate how learned indexes behave at a micro-architectural level compared to traditional indexes. More specifically, we focus on previously proposed learned index structure ALEX, which is a tree-based in-memory index structure that consists of a hierarchy of machine learned models. Unlike the original proposal for learned indexes, ALEX is designed from the ground up to allow updates and inserts. Therefore, it enables more dynamic workloads using learned indexes. In this work, we perform a micro-architectural analysis of ALEX and compare its behavior to the tree-based index structures that are not based on learned models, i.e., ART and B+Tree. Our results show that ALEX is bound by memory stalls, mainly stalls due to data misses from the last-level cache. Compared to ART and B+Tree, ALEX exhibits fewer stalls and a lower cycles-per-instruction value across different workloads. On the other hand, the amount of instructions required to handle out-of-bound inserts in ALEX can increase the instructions needed per request significantly (10X) for write-heavy workloads. However, the micro-architectural behavior shows that this increase in the instruction footprint exhibit high instruction-level parallelism, and, therefore, does not negatively impact the overall execution time.
• Abstract（参考訳）: 2018年にThe Case for Learned Index Structuresが出版されて以来、異なるドメインと異なる機能を持つ学習インデックスに焦点を当てた研究が増えている。 B+Treesのような従来のインデックス構造に代わる学習インデックスの有効性はすでにいくつかの研究で実証されているが、以前の研究はスループットやインデックスサイズといったハイレベルなパフォーマンス指標に重点を置いていた。 本稿では,従来の指標と比較して,学習指標が微構造レベルでどのように振る舞うかを深く研究することを目的とする。 具体的には、先述した学習インデックス構造であるalexに注目した。alexは、機械学習モデルの階層構造からなる、ツリーベースのインメモリインデックス構造である。 学習インデックスに関する当初の提案とは異なり、ALEXはアップデートと挿入を可能にするためにゼロから設計されている。 したがって、学習インデックスを使用して、よりダイナミックなワークロードを可能にする。 本研究では、ALEXの微構造解析を行い、その挙動を学習モデル(ARTとB+Tree)に基づいていない木に基づく指標構造と比較する。 以上の結果から,ALEXはメモリストールによってバインドされていることが明らかとなった。 ARTやB+Treeと比較して、ALEXはストールが少なく、異なるワークロード間でのインストラクションあたりのサイクル値が低い。 一方、ALEXのアウトオブバウンドインサートを処理するために必要なインストラクションの量は、書き込み重負荷に対するリクエスト毎の命令(10X)を大幅に増加させる可能性がある。 しかし、マイクロアーキテクチャの挙動は、この命令フットプリントの増加は高い命令レベルの並列性を示し、従って全体の実行時間に悪影響を及ぼさないことを示している。

関連論文リスト

• Semi-Parametric Retrieval via Binary Token Index [71.78109794895065]
  Semi-parametric Vocabulary Disentangled Retrieval (SVDR) は、新しい半パラメトリック検索フレームワークである。 既存のニューラル検索手法に似た、高い有効性のための埋め込みベースのインデックスと、従来の用語ベースの検索に似た、迅速かつ費用対効果の高いセットアップを可能にするバイナリトークンインデックスの2つのタイプをサポートする。 埋め込みベースインデックスを使用する場合の高密度検索器DPRよりも3%高いトップ1検索精度と、バイナリトークンインデックスを使用する場合のBM25よりも9%高いトップ1検索精度を実現する。
  論文  参考訳（メタデータ） (2024-05-03T08:34:13Z)
• EHI: End-to-end Learning of Hierarchical Index for Efficient Dense Retrieval [18.15717995719973]
  EHI(End-to-end Hierarchical Indexing)は埋め込み型検索の新しい手法である。 EHIは、MS MARCO (Dev) の MRR@10 で +1.45% 、TREC DL19 の nDCG@10 で +8.2% で、既存の最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-10-13T06:53:02Z)
• End-to-End Learning to Index and Search in Large Output Spaces [95.16066833532396]
  Extreme Multi-label Classification (XMC) は現実世界の問題を解決するための一般的なフレームワークである。 本稿では,木系インデックスを特殊重み付きグラフベースインデックスに緩和する新しい手法を提案する。 ELIASは、数百万のラベルを持つ大規模極端分類ベンチマークで最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2022-10-16T01:34:17Z)
• LSI: A Learned Secondary Index Structure [24.324528705706104]
  本研究では,未分類データのインデックス化に学習指標を使用する最初の試みであるLearnered secondary Index(LSI)を紹介する。 LSIは最先端のセカンダリインデックスに匹敵するルックアップ性能を実現し,空間効率を最大6倍に向上することを示す。
  論文  参考訳（メタデータ） (2022-05-11T20:49:44Z)
• Autoregressive Search Engines: Generating Substrings as Document Identifiers [53.0729058170278]
  自動回帰言語モデルは、回答を生成するデファクト標準として現れています。 これまでの研究は、探索空間を階層構造に分割する方法を探究してきた。 本研究では,検索空間の任意の構造を強制しない代替として,経路内のすべてのngramを識別子として使用することを提案する。
  論文  参考訳（メタデータ） (2022-04-22T10:45:01Z)
• CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm [1.9798034349981157]
  Recursive Model Index (RMI) フレームワークの効率を改善するために,キャッシュ認識型学習インデックス (CARMI) の設計を提案する。 学習指標の最適設計を最適化問題として探索する問題を定式化し,それを解くための動的プログラミングアルゴリズムを提案する。 実験の結果,ベースラインよりも高い性能でインデックスを構築することができることがわかった。
  論文  参考訳（メタデータ） (2021-03-01T09:20:53Z)
• A Pluggable Learned Index Method via Sampling and Gap Insertion [48.900186573181735]
  データベースインデックスは、データ検索を促進し、現実世界のシステムにおける幅広いアプリケーションに役立つ。 近年,隠れて有用なデータ分布を学習するために,learning indexという新しいインデックスが提案されている。 学習指標の学習効率と学習効率を高めるための2つの一般的なテクニックとプラグイン可能なテクニックを研究します。
  論文  参考訳（メタデータ） (2021-01-04T07:17:23Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  我々は、空間範囲の問合せに答えるために、最先端の学習した多次元インデックス構造(すなわちFlood)から提案した手法を用いる。 i) パーティション内の機械学習検索は、1次元でフィルタリングを使用する場合の2進探索よりも11.79%速く、39.51%高速であることを示す。 また、2次元でフィルタする最も近い競合相手の1.23倍から1.83倍の速さで機械学習インデックスを精査する。
  論文  参考訳（メタデータ） (2020-08-24T12:09:55Z)
• COAX: Correlation-Aware Indexing on Multidimensional Data with Soft Functional Dependencies [3.670422696827525]
  データセットの属性間の相関関係を学習する多次元データのための学習指標であるCOAXを提案する。 実験により,データ中の関連属性を予測することにより,クエリ実行時間を短縮し,インデックスのメモリオーバーヘッドを低減することができることがわかった。
  論文  参考訳（メタデータ） (2020-06-29T21:22:15Z)
• Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads [29.223401893397714]
  我々は,既存の学習した多次元インデックスよりも最大6倍高速なクエリ性能と最大8倍のインデックスサイズを実現する綱見を紹介した。
  論文  参考訳（メタデータ） (2020-06-23T19:25:51Z)
• RadixSpline: A Single-Pass Learned Index [84.84747738666263]
  RadixSpline(RS)は、データに1回のパスで構築できる学習インデックスです。 RSは2つのパラメータしか持たないにもかかわらず、すべてのデータセットで競合的な結果を達成する。
  論文  参考訳（メタデータ） (2020-04-30T01:56:54Z)

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

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