論文の概要: Learning-Augmented Skip Lists

• arxiv url: http://arxiv.org/abs/2402.10457v1
• Date: Fri, 16 Feb 2024 05:27:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-02-19 17:32:37.122782
• Title: Learning-Augmented Skip Lists
• Title（参考訳）: 学習型スキップリスト
• Authors: Chunkai Fu, Jung Hoon Seo, Samson Zhou
• Abstract要約: 我々は、従来のデータ構造設計を改善するために、スキップリストの設計への機械学習アドバイスの統合について検討する。 2倍近い確率で最適な探索時間を確実に提供するスキップリストを構築した。 我々の学習強化スキップリストは、たとえオラクルが定数係数内でのみ正確であっても、まだ定数係数まで最適である。
• 参考スコア（独自算出の注目度）: 19.561534602715792
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the integration of machine learning advice into the design of skip lists to improve upon traditional data structure design. Given access to a possibly erroneous oracle that outputs estimated fractional frequencies for search queries on a set of items, we construct a skip list that provably provides the optimal expected search time, within nearly a factor of two. In fact, our learning-augmented skip list is still optimal up to a constant factor, even if the oracle is only accurate within a constant factor. We show that if the search queries follow the ubiquitous Zipfian distribution, then the expected search time for an item by our skip list is only a constant, independent of the total number $n$ of items, i.e., $\mathcal{O}(1)$, whereas a traditional skip list will have an expected search time of $\mathcal{O}(\log n)$. We also demonstrate robustness by showing that our data structure achieves an expected search time that is within a constant factor of an oblivious skip list construction even when the predictions are arbitrarily incorrect. Finally, we empirically show that our learning-augmented skip list outperforms traditional skip lists on both synthetic and real-world datasets.
• Abstract（参考訳）: 従来のデータ構造設計を改善するために、スキップリストの設計に機械学習のアドバイスを統合することを検討する。 一組の項目で検索クエリに対して推定された分数頻度を出力する誤ったオラクルにアクセスすると、2倍近い確率で最適な検索時間を確実に提供するスキップリストを構築する。 実際、私たちの学習によるスキップリストは、たとえオラクルが一定要素内でのみ正確であっても、一定要素まで最適です。 検索クエリがユビキタスZipfian分布に従えば、スキップリストによるアイテムの検索時間は一定であり、アイテムの総数$n$(例えば$\mathcal{O}(1)$)とは独立であるのに対し、従来のスキップリストは$\mathcal{O}(\log n)$と期待される検索時間を持つ。 また, 予測が任意に誤りである場合でも, 不可能なスキップリスト構築の一定要素内にある検索時間をデータ構造が達成できることを示し, 頑健性を示す。 最後に、私たちの学習によるスキップリストが、合成データと実世界のデータセットの両方で従来のスキップリストを上回っていることを実証的に示します。

関連論文リスト

• 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)

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

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