論文の概要: 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 19:13:14.536862
• 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: http://creativecommons.org/licenses/by/4.0/
• 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ツリー構築の一定要素内にある検索時間をデータ構造が達成できることを示し, 頑健性を示す。 最後に、我々の学習強化された検索データ構造が、合成データセットと実世界のデータセットの両方において、従来のアナログよりも優れていることを実証的に示す。

関連論文リスト

• Linked Array Tree: A Constant-Time Search Structure for Big Data [0.0]
  Linked Array Tree (LAT) は、検索、挿入、削除操作の時間的複雑さを実現するために設計された新しいデータ構造である。 LATの低メモリオーバーヘッドとポインタ重構造の回避は、大規模かつ集中的なワークロードに適しています。
  論文  参考訳（メタデータ） (2025-04-01T14:15:55Z)
• Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
  本稿では,予測決定木アンサンブルを学習するためのハイブリッドアモータイズされた構造推論手法を提案する。 提案手法であるDT-GFNは,標準分類ベンチマークにおける最先端決定木やディープラーニング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-03-10T07:05:07Z)
• A Query-Driven Approach to Space-Efficient Range Searching [12.760453906939446]
  クエリのほぼ直線的なサンプルは、クエリ中に訪れたノード数がほぼ最適であるパーティションツリーを構築することができることを示す。 我々は、ノード処理を分類問題として扱い、浅いニューラルネットワークのような高速な分類器を活用して、実験的に効率的なクエリ時間を得ることにより、このアプローチを強化する。 我々のアルゴリズムは,クエリのサンプルに基づいて,セパレータに関連付けられたノードを持つバランスのとれたツリーを構築し,クエリの待ち行列を最小化する。
  論文  参考訳（メタデータ） (2025-02-19T12:01:00Z)
• BPP-Search: Enhancing Tree of Thought Reasoning for Mathematical Modeling Problem Solving [11.596474985695679]
  我々は、完全な数学的モデリングプロセスをキャプチャする包括的ラベルを付したStructuredORデータセットをリリースする。 本稿では,強化学習をツリー・オブ・シント構造に統合するアルゴリズムであるBPP-Searchを提案する。 木に基づく推論では、BPP-Searchは精度と効率が優れ、正しい解の高速な検索を可能にする。
  論文  参考訳（メタデータ） (2024-11-26T13:05:53Z)
• Discovering Data Structures: Nearest Neighbor Search and Beyond [18.774836778996544]
  データ構造をエンド・ツー・エンドで学習するための一般的なフレームワークを提案する。 我々のフレームワークは、基礎となるデータ分布に適応し、クエリと空間の複雑さをきめ細やかな制御を提供する。 まず、この枠組みを近接探索問題に適用する。
  論文  参考訳（メタデータ） (2024-11-05T16:50:54Z)
• Understanding Synthetic Context Extension via Retrieval Heads [51.8869530817334]
  本稿では,検索と推論を必要とする3つの長文タスクに対する合成データの微調整について検討する。 合成データに基づいてトレーニングされたモデルは、実際のデータには及ばないが、驚くべきことに、ミスマッチを解釈できる。 我々の結果は、合成データの微調整性能の解釈方法と、長期にわたる実世界の能力学習のためのより良いデータ作成方法に光を当てた。
  論文  参考訳（メタデータ） (2024-10-29T17:55:00Z)
• 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)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• 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)
• 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 List Labeling with Predictions [13.126494821223755]
  オンラインリストラベリングの基本的な問題において,予測が活用可能であることを示す。 問題では、n個のアイテムが時間とともに到着し、サイズ Theta(n) の配列でソートされた順序で格納されなければならない。 データ構造をラベル付けした新しいリストを設計し、その性能を2つのモデルでバインドする。
  論文  参考訳（メタデータ） (2023-05-17T19:46:34Z)
• Online Learning of Optimally Diverse Rankings [63.62764375279861]
  ユーザのフィードバックのみに基づいて最適なリストを効率よく学習するアルゴリズムを提案する。 我々は、$T$クエリの後に、LDRの後悔は$O((N-L)log(T))$としてスケールする。
  論文  参考訳（メタデータ） (2021-09-13T12:13:20Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  本研究では,高次元scRNA-seqデータから意味のある木構造を同定する手法を提案する。 次に、低次元空間におけるデータのツリー構造を強調する木バイアスオートエンコーダDTAEを紹介する。
  論文  参考訳（メタデータ） (2021-02-11T08:48:48Z)
• Surprise: Result List Truncation via Extreme Value Theory [92.5817701697342]
  そこで本研究では,問合せ時における可逆的・校正的関連度スコアを,ランク付けされたスコアに留まらず,統計的に生成する手法を提案する。 本稿では、画像、テキスト、IRデータセット間での結果リストのトランケーションタスクにおいて、その効果を実証する。
  論文  参考訳（メタデータ） (2020-10-19T19:15:50Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)
• 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)
• Tree Echo State Autoencoders with Grammars [3.7280152311394827]
  木の非ベクトル的かつ離散的な性質は、木形式の出力を持つ関数を構築するのを難しくする。 既存のオートエンコーディングアプローチは、ツリードメインの特定の文法構造を考慮に入れない。 本研究では,木文法でガイドされる木エコー状態オートエンコーダ(TES-AE)を提案する。
  論文  参考訳（メタデータ） (2020-04-19T18:04:33Z)
• 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)

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

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