論文の概要: Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform

• arxiv url: http://arxiv.org/abs/2201.01554v1
• Date: Wed, 5 Jan 2022 11:46:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-06 17:19:43.453330
• Title: Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platform
• Title（参考訳）: 学習静的インデックス作成における標準Vs一様二項探索とその変数--Sorted Data Benchmarking Software Platform上での検索を事例として
• Authors: Domenico Amato, Giosu\`e Lo Bosco, Raffaele Giancarlo
• Abstract要約: 学習者にとって、bf SOSDソフトウェアに関して、標準ルーチンの使用はUniformよりも優れていることを示す。 実験の結果,一様二項探索とk-ary Searchは学習空間の節約に有用であることが示唆された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Searching on Sorted Data ({\bf SOSD}, in short) is a highly engineered software platform for benchmarking Learned Indexes, those latter being a novel and quite effective proposal of how to search in a sorted table by combining Machine Learning techniques with classic Algorithms. In such a platform and in the related benchmarking experiments, following a natural and intuitive choice, the final search stage is performed via the Standard (textbook) Binary Search procedure. However, recent studies, that do not use Machine Learning predictions, indicate that Uniform Binary Search, streamlined to avoid \vir{branching} in the main loop, is superior in performance to its Standard counterpart when the table to be searched into is relatively small, e.g., fitting in L1 or L2 cache. Analogous results hold for k-ary Search, even on large tables. One would expect an analogous behaviour within Learned Indexes. Via a set of extensive experiments, coherent with the State of the Art, we show that for Learned Indexes, and as far as the {\bf SOSD} software is concerned, the use of the Standard routine (either Binary or k-ary Search) is superior to the Uniform one, across all the internal memory levels. This fact provides a quantitative justification of the natural choice made so far. Our experiments also indicate that Uniform Binary and k-ary Search can be advantageous to use in order to save space in Learned Indexes, while granting a good performance in time. Our findings are of methodological relevance for this novel and fast-growing area and informative to practitioners interested in using Learned Indexes in application domains, e.g., Data Bases and Search Engines.
• Abstract（参考訳）: The Searching on Sorted Data(略して{\bf SOSD)は、機械学習技術と古典的なアルゴリズムを組み合わせることで、ソートされたテーブルで検索する方法を新しく、非常に効果的な提案である学習インデックスをベンチマークするための高度に設計されたソフトウェアプラットフォームである。 このようなプラットフォームと関連するベンチマーク実験では、自然で直感的な選択に従って、最終探索段階は標準 (textbook) バイナリサーチによって実行される。 しかし、機械学習の予測を使用しない最近の研究は、主ループで \vir{branching} を避けるために合理化されている統一バイナリ検索が、L1 や L2 キャッシュに適合するなど、検索対象のテーブルが比較的小さい場合、その標準よりも性能が優れていることを示している。 k-ary Searchの結果は、大きなテーブルでも参照できる。 Learned Indexesに類似した振る舞いが期待できる。 最先端技術(State of the Art)に忠実な一連の実験により、学習指標(Learnered Indexes)に対して、標準ルーチン(バイナリまたはk-ary Search)の使用は、すべての内部メモリレベルにおいて、Uniformよりも優れていることを示す。 この事実は、これまでの自然選択を定量的に正当化する。 また,一様二項探索とk-ary Searchは,学習インデックスにおける空間の保存に有効であり,時間的性能も良好であることを示す。 本研究は,この新規かつ急速に成長する領域の方法論的意義と,アプリケーションドメイン,例えばデータベースや検索エンジンにおける学習指標の利用に関心のある実践者への情報提供について考察した。

関連論文リスト

• Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes? [62.57689536630933]
  本稿では,オープンソースのLucene検索ライブラリを用いたBEIRデータセットの実験結果について述べる。 本研究は,高密度かつ疎密なレトリバーの設計空間を理解するための,今日の検索実践者へのガイダンスを提供する。
  論文  参考訳（メタデータ） (2024-09-10T12:46:23Z)
• 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)
• From Specific to Generic Learned Sorted Set Dictionaries: A Theoretically Sound Paradigm Yelding Competitive Data Structural Boosters in Practice [0.0]
  我々は学習されたセット辞書に焦点をあてる。 我々は、既知の専門用語を補完する新しいパラダイムを提案し、任意のSorted Set Dictionaryの学習版を作成できる。
  論文  参考訳（メタデータ） (2023-09-02T13:52:53Z)
• A Large Scale Search Dataset for Unbiased Learning to Rank [51.97967284268577]
  我々は、非バイアス学習のためのBaidu-ULTRデータセットをランク付けする。 ランダムに12億の検索セッションと7,008のエキスパートアノテートクエリをサンプリングする。 1)本来のセマンティックな特徴と,使用が容易な事前学習言語モデル,(2)位置,表示高さ,抽象表現などの十分な表示情報,(3)居住時間のような検索結果ページ(SERP)に対するリッチなユーザフィードバックを提供する。
  論文  参考訳（メタデータ） (2022-07-07T02:37:25Z)
• LSI: A Learned Secondary Index Structure [24.324528705706104]
  本研究では,未分類データのインデックス化に学習指標を使用する最初の試みであるLearnered secondary Index(LSI)を紹介する。 LSIは最先端のセカンダリインデックスに匹敵するルックアップ性能を実現し,空間効率を最大6倍に向上することを示す。
  論文  参考訳（メタデータ） (2022-05-11T20:49:44Z)
• Learned Sorted Table Search and Static Indexes in Small Space: Methodological and Practical Insights via an Experimental Study [0.0]
  Sorted Table Search プロシージャはクインテシデントなクエリ検索ツールだが,それでも非常に有用だ。 検索するテーブルに関して、小さな追加スペースでそれらをスピードアップすることは、依然として非常に大きな成果である。 一定あるいはほぼ一定の追加空間を使用しながら、学習のスピードアップをどの程度楽しむことができるかは、大きな疑問である。
  論文  参考訳（メタデータ） (2021-07-19T16:06:55Z)
• 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)
• Learning from Data to Speed-up Sorted Table Search Procedures: Methodology and Practical Guidelines [0.0]
  機械学習技術の拡張が、このようなスピードアップにどのような貢献をできるかを調査する。 我々は、CPUおよびGPUコンピューティングの両方を考慮して、後者が前者に対して利益を上げることができるシナリオを特徴づける。 実際、ここで提案した学習表検索手順を自然に補完するアルゴリズム的パラダイムを定式化し、既知の学習表検索手順の大部分を、単純な線形回帰を近似した「学習フェーズ」を持つものとして特徴付ける。
  論文  参考訳（メタデータ） (2020-07-20T16:26:54Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)
• Progressively Pretrained Dense Corpus Index for Open-Domain Question Answering [87.32442219333046]
  本稿では,段落エンコーダを事前学習するための簡易かつ資源効率の高い手法を提案する。 本手法は,事前学習に7倍の計算資源を使用する既存の高密度検索法より優れている。
  論文  参考訳（メタデータ） (2020-04-30T18:09:50Z)

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

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