論文の概要: On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing
- arxiv url: http://arxiv.org/abs/2306.10651v1
- Date: Mon, 19 Jun 2023 00:00:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-21 19:27:06.422674
- Title: On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing
- Title（参考訳）: 学習インデクシングの分布依存部分対数問合せ時間について
- Authors: Sepanta Zeighami, Cyrus Shahabi
- Abstract要約: データ管理の根本的な問題は、クエリにマッチする配列内の要素を見つけることだ。
近年,この問題を解決するために学習指標が広く利用されている。
これらは経験的に、未学習の手法を桁違いに上回ることが示される。
- 参考スコア（独自算出の注目度）: 8.758701819897508
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A fundamental problem in data management is to find the elements in an array
that match a query. Recently, learned indexes are being extensively used to
solve this problem, where they learn a model to predict the location of the
items in the array. They are empirically shown to outperform non-learned
methods (e.g., B-trees or binary search that answer queries in $O(\log n)$
time) by orders of magnitude. However, success of learned indexes has not been
theoretically justified. Only existing attempt shows the same query time of
$O(\log n)$, but with a constant factor improvement in space complexity over
non-learned methods, under some assumptions on data distribution. In this
paper, we significantly strengthen this result, showing that under mild
assumptions on data distribution, and the same space complexity as non-learned
methods, learned indexes can answer queries in $O(\log\log n)$ expected query
time. We also show that allowing for slightly larger but still near-linear
space overhead, a learned index can achieve $O(1)$ expected query time. Our
results theoretically prove learned indexes are orders of magnitude faster than
non-learned methods, theoretically grounding their empirical success.
- Abstract（参考訳）: データ管理の根本的な問題は、クエリにマッチする配列内の要素を見つけることだ。
近年、この問題を解決するために学習インデックスが広く使われており、配列内のアイテムの位置を予測するモデルを学習している。
これらは、非学習メソッド(例えば、o(\log n)$ time でクエリに応答する b-trees やバイナリ検索)を桁違いに上回っていることが実証的に示されている。
しかし、学習インデックスの成功は理論的に正当化されていない。
既存の試行だけが$O(\log n)$と同じクエリ時間を示しているが、データ分散に関するいくつかの仮定の下で、非学習メソッドよりも空間の複雑さが一定に改善されている。
本稿では,データ分散の軽度な仮定と,非学習手法と同じ空間の複雑さにより,学習インデックスが$O(\log\log n)$予測クエリ時間でクエリに答えられることを示す。
また,少し大きくてもニアリニアな空間のオーバーヘッドを許すことで,学習インデックスが$o(1)$ のクエリ時間を達成できることを示した。
本研究は,学習指標が非学習法よりも桁違いに高速であることを理論的に証明し,その経験的成功を理論的に基礎づけた。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search [24.85572470526277]
周辺地域を探索するRFANN(Range-filtering Near Near Near Near neighbor)は、学術や産業で注目を集めている。
最近の研究では、可能な全てのクエリ範囲に対して、$O(n2)$専用のグラフベースのインデックスを構築することを提案する。
要素グラフと呼ばれるグラフベースのインデックスを適度な範囲で作成する。
論文 参考訳（メタデータ） (2024-09-04T09:41:52Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - LSI: A Learned Secondary Index Structure [24.324528705706104]
本研究では,未分類データのインデックス化に学習指標を使用する最初の試みであるLearnered secondary Index(LSI)を紹介する。
LSIは最先端のセカンダリインデックスに匹敵するルックアップ性能を実現し,空間効率を最大6倍に向上することを示す。
論文 参考訳（メタデータ） (2022-05-11T20:49:44Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳（メタデータ） (2021-10-05T20:15:35Z) - 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) - IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。
クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。
我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文 参考訳（メタデータ） (2021-03-17T23:13:25Z) - 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) - COAX: Correlation-Aware Indexing on Multidimensional Data with Soft
Functional Dependencies [3.670422696827525]
データセットの属性間の相関関係を学習する多次元データのための学習指標であるCOAXを提案する。
実験により,データ中の関連属性を予測することにより,クエリ実行時間を短縮し,インデックスのメモリオーバーヘッドを低減することができることがわかった。
論文 参考訳（メタデータ） (2020-06-29T21:22:15Z) - Tsunami: A Learned Multi-dimensional Index for Correlated Data and
Skewed Workloads [29.223401893397714]
我々は,既存の学習した多次元インデックスよりも最大6倍高速なクエリ性能と最大8倍のインデックスサイズを実現する綱見を紹介した。
論文 参考訳（メタデータ） (2020-06-23T19:25:51Z) - RadixSpline: A Single-Pass Learned Index [84.84747738666263]
RadixSpline(RS)は、データに1回のパスで構築できる学習インデックスです。
RSは2つのパラメータしか持たないにもかかわらず、すべてのデータセットで競合的な結果を達成する。
論文 参考訳（メタデータ） (2020-04-30T01:56:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。