論文の概要: Learning-Augmented Search Data Structures

• arxiv url: http://arxiv.org/abs/2402.10457v2
• Date: Fri, 07 Mar 2025 16:10:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-10 12:20:37.550756
• Title: Learning-Augmented Search Data Structures
• Title（参考訳）: 学習強化検索データ構造
• Authors: Chunkai Fu, Brandon G. Nguyen, Jung Hoon Seo, Ryan Zesch, Samson Zhou,
• Abstract要約: 本研究では,効率的な検索クエリのために設計された従来のデータ構造を改善するために,機械学習アドバイスの統合について検討する。 スキップリストとKDツリーを構築し、2倍近い確率で最適な探索時間を提供する。 実際、我々の学習強化されたスキップリストとKDツリーは、たとえオラクルが一定要素内でのみ正確であっても、まだ一定要素まで最適である。
• 参考スコア（独自算出の注目度）: 14.015114340879544
• License:
• Abstract: We study the integration of machine learning advice to improve upon traditional data structure designed for efficient search queries. Although there has been recent effort in improving the performance of binary search trees using machine learning advice, e.g., Lin et. al. (ICML 2022), the resulting constructions nevertheless suffer from inherent weaknesses of binary search trees, such as complexity of maintaining balance across multiple updates and the inability to handle partially-ordered or high-dimensional datasets. For these reasons, we focus on skip lists and KD trees in this work. Given access to a possibly erroneous oracle that outputs estimated fractional frequencies for search queries on a set of items, we construct skip lists and KD trees that provably provides the optimal expected search time, within nearly a factor of two. In fact, our learning-augmented skip lists and KD trees are still optimal up to a constant factor, even if the oracle is only accurate within a constant factor. We also demonstrate robustness by showing that our data structures achieves an expected search time that is within a constant factor of an oblivious skip list/KD tree construction even when the predictions are arbitrarily incorrect. Finally, we empirically show that our learning-augmented search data structures outperforms their corresponding traditional analogs on both synthetic and real-world datasets.
• Abstract（参考訳）: 本研究では,効率的な検索クエリのために設計された従来のデータ構造を改善するために,機械学習アドバイスの統合について検討する。 機械学習のアドバイス(例:Lin et al (ICML 2022))を使った二分探索木の性能向上への取り組みは近年行われているが、結果として得られた構造は、複数の更新をまたいでバランスを維持する複雑さや、部分的に順序付けされた、あるいは高次元のデータセットを扱うことができないなど、二分探索木固有の弱点に悩まされている。 これらの理由から、この作業ではスキップリストとKDツリーに重点を置いています。 一組のアイテムで検索クエリに対して推定された分数頻度を出力する、おそらく誤ったオラクルへのアクセスを前提として、スキップリストとKDツリーを構築し、ほぼ2倍の確率で最適な検索時間を提供する。 実際、我々の学習強化されたスキップリストとKDツリーは、たとえオラクルが一定要素内でのみ正確であっても、まだ一定要素まで最適である。 また, 予測が任意に誤りである場合でも, 不可解なスキップリスト/KDツリー構築の一定要素内にある検索時間をデータ構造が達成できることを示し, 頑健性を示す。 最後に、我々の学習強化された検索データ構造が、合成データセットと実世界のデータセットの両方において、従来のアナログよりも優れていることを実証的に示す。

関連論文リスト

• Pairing Clustered Inverted Indexes with kNN Graphs for Fast Approximate Retrieval over Learned Sparse Representations [8.796275989527054]
  本稿では,高精度な近似探索アルゴリズムである地震探査について述べる。 地震は、最先端の逆インデックスベースのソリューションよりも1～2桁高速である。 まず、任意にではなく、重要な順にブロックを横断する。 我々の拡張は、地震波と呼ばれ、ほぼ正確に、地震の2.2倍の速さで到達することができる。
  論文  参考訳（メタデータ） (2024-08-08T13:14:39Z)
• LIST: Learning to Index Spatio-Textual Data for Embedding based Spatial Keyword Queries [53.843367588870585]
  リスト K-kNN 空間キーワードクエリ (TkQ) は、空間的およびテキスト的関連性の両方を考慮したランキング関数に基づくオブジェクトのリストを返す。 効率的かつ効率的な指標、すなわち高品質なラベルの欠如とバランスの取れない結果を構築する上で、大きな課題が2つある。 この2つの課題に対処する新しい擬似ラベル生成手法を開発した。
  論文  参考訳（メタデータ） (2024-03-12T05:32:33Z)
• CodeComplex: Dataset for Worst-Case Time Complexity Prediction [7.974618854858136]
  コード時間の複雑さ予測には、変数の入力範囲や条件ループなど、様々な複雑な要素が含まれる。 現在のベンチマークは、限られたデータ、言語制約、不十分なラベリングのために厳格な評価を提供していない。 コード時間の複雑さを予測する上で,LSMの推論能力を評価するために設計された最初の堅牢で広範なデータセットであるCodeComplexを紹介した。
  論文  参考訳（メタデータ） (2024-01-16T06:54:44Z)
• Found in the Middle: Permutation Self-Consistency Improves Listwise Ranking in Large Language Models [63.714662435555674]
  大規模言語モデル(LLM)は、文脈の使い方に位置バイアスを示す。 我々は,ブラックボックスLLMのランキングリスト出力に対して,自己整合性(permutation self-consistency)を提案する。 LLaMA v2 (70B) では GPT-3.5 では 7-18% , LLaMA v2 (70B) では 8-16% である。
  論文  参考訳（メタデータ） (2023-10-11T17:59:02Z)
• 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)
• Online Learning of Optimally Diverse Rankings [63.62764375279861]
  ユーザのフィードバックのみに基づいて最適なリストを効率よく学習するアルゴリズムを提案する。 我々は、$T$クエリの後に、LDRの後悔は$O((N-L)log(T))$としてスケールする。
  論文  参考訳（メタデータ） (2021-09-13T12:13:20Z)
• Surprise: Result List Truncation via Extreme Value Theory [92.5817701697342]
  そこで本研究では,問合せ時における可逆的・校正的関連度スコアを,ランク付けされたスコアに留まらず,統計的に生成する手法を提案する。 本稿では、画像、テキスト、IRデータセット間での結果リストのトランケーションタスクにおいて、その効果を実証する。
  論文  参考訳（メタデータ） (2020-10-19T19:15:50Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)
• RadixSpline: A Single-Pass Learned Index [84.84747738666263]
  RadixSpline(RS)は、データに1回のパスで構築できる学習インデックスです。 RSは2つのパラメータしか持たないにもかかわらず、すべてのデータセットで競合的な結果を達成する。
  論文  参考訳（メタデータ） (2020-04-30T01:56:54Z)
• Increasing the Inference and Learning Speed of Tsetlin Machines with Clause Indexing [9.440900386313215]
  Tsetlin Machine (TM) は、古典的なTsetlin Automaton (TA) とゲーム理論に基づいて開発された機械学習アルゴリズムである。 我々は,MNISTとFashion-MNISTの画像分類とIMDbの感情分析を最大15倍,学習速度が3倍に向上したことを報告した。
  論文  参考訳（メタデータ） (2020-04-07T08:16:07Z)

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

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