論文の概要: 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)$と期待される検索時間を持つ。 また, 予測が任意に誤りである場合でも, 不可能なスキップリスト構築の一定要素内にある検索時間をデータ構造が達成できることを示し, 頑健性を示す。 最後に、私たちの学習によるスキップリストが、合成データと実世界のデータセットの両方で従来のスキップリストを上回っていることを実証的に示します。

関連論文リスト

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

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

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