論文の概要: Learned Sorted Table Search and Static Indexes in Small Space:
Methodological and Practical Insights via an Experimental Study
- arxiv url: http://arxiv.org/abs/2107.09480v2
- Date: Wed, 21 Jul 2021 13:56:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-22 11:21:39.334167
- Title: Learned Sorted Table Search and Static Indexes in Small Space:
Methodological and Practical Insights via an Experimental Study
- Title（参考訳）: 小空間における学習表検索と静的指数:実験による方法論的・実践的考察
- Authors: Domenico Amato and Raffaele Giancarlo and Giosu\`e Lo Bosco
- Abstract要約: Sorted Table Search プロシージャはクインテシデントなクエリ検索ツールだが,それでも非常に有用だ。
検索するテーブルに関して、小さな追加スペースでそれらをスピードアップすることは、依然として非常に大きな成果である。
一定あるいはほぼ一定の追加空間を使用しながら、学習のスピードアップをどの程度楽しむことができるかは、大きな疑問である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sorted Table Search Procedures are the quintessential query-answering tool,
still very useful, e.g, Search Engines (Google Chrome). Speeding them up, in
small additional space with respect to the table being searched into, is still
a quite significant achievement. Static Learned Indexes have been very
successful in achieving such a speed-up, but leave open a major question: To
what extent one can enjoy the speed-up of Learned Indexes while using constant
or nearly constant additional space. By generalizing the experimental
methodology of a recent benchmarking study on Learned Indexes, we shed light on
this question, by considering two scenarios. The first, quite elementary, i.e.,
textbook code, and the second using advanced Learned Indexing algorithms and
the supporting sophisticated software platforms. Although in both cases one
would expect a positive answer, its achievement is not as simple as it seems.
Indeed, our extensive set of experiments reveal a complex relationship between
query time and model space. The findings regarding this relationship and the
corresponding quantitative estimates, across memory levels, can be of interest
to algorithm designers and of use to practitioners as well. As an essential
part of our research, we introduce two new models that are of interest in their
own right. The first is a constant space model that can be seen as a
generalization of $k$-ary search, while the second is a synoptic {\bf RMI}, in
which we can control model space usage.
- Abstract（参考訳）: Sorted Table Search proceduresは、検索エンジン(Google Chrome)など、非常に有用なクエリー回答ツールである。
検索されるテーブルに関して、小さな追加スペースでそれらをスピードアップすることは、依然として非常に大きな成果です。
静的学習インデックスはこのようなスピードアップを達成するのに非常に成功していますが、大きな疑問が残っています。
学習指標に関する最近のベンチマーク研究の実験方法論を一般化することにより、2つのシナリオを考慮し、この問題に光を当てた。
第一は、非常に初歩的な、すなわち教科書のコードで、第二は高度な学習インデックスアルゴリズムと高度なソフトウェアプラットフォームを使用する。
どちらの場合も肯定的な答えを期待するが、その達成は見かけほど単純ではない。
実際、我々の広範な実験のセットは、クエリ時間とモデル空間の間の複雑な関係を明らかにする。
この関係に関する知見と、それに対応するメモリレベルの定量的推定は、アルゴリズム設計者や実践者にとっても興味深いものである。
私たちの研究の重要な部分として、独自の関心を持つ2つの新しいモデルを紹介します。
1つは定数空間モデルであり、$k$-ary searchの一般化と見なすことができ、もう1つはシントロピック {\bf RMI} であり、モデル空間の使用を制御できる。
関連論文リスト
- Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes? [62.57689536630933]
本稿では,オープンソースのLucene検索ライブラリを用いたBEIRデータセットの実験結果について述べる。
本研究は,高密度かつ疎密なレトリバーの設計空間を理解するための,今日の検索実践者へのガイダンスを提供する。
論文 参考訳（メタデータ） (2024-09-10T12:46:23Z) - 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) - Searching a High-Performance Feature Extractor for Text Recognition
Network [92.12492627169108]
優れた特徴抽出器を持つための原理を探求し,ドメイン固有の検索空間を設計する。
空間は巨大で複雑な構造であるため、既存のNASアルゴリズムを適用することはできない。
本研究では,空間内を効率的に探索する2段階のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-27T03:49:04Z) - A Large Scale Search Dataset for Unbiased Learning to Rank [51.97967284268577]
我々は、非バイアス学習のためのBaidu-ULTRデータセットをランク付けする。
ランダムに12億の検索セッションと7,008のエキスパートアノテートクエリをサンプリングする。
1)本来のセマンティックな特徴と,使用が容易な事前学習言語モデル,(2)位置,表示高さ,抽象表現などの十分な表示情報,(3)居住時間のような検索結果ページ(SERP)に対するリッチなユーザフィードバックを提供する。
論文 参考訳（メタデータ） (2022-07-07T02:37:25Z) - Standard Vs Uniform Binary Search and Their Variants in Learned Static
Indexing: The Case of the Searching on Sorted Data Benchmarking Software
Platform [0.0]
学習者にとって、bf SOSDソフトウェアに関して、標準ルーチンの使用はUniformよりも優れていることを示す。
実験の結果,一様二項探索とk-ary Searchは学習空間の節約に有用であることが示唆された。
論文 参考訳（メタデータ） (2022-01-05T11:46:16Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。
我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。
提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
論文 参考訳（メタデータ） (2021-12-05T06:42:48Z) - 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) - Learning from Data to Speed-up Sorted Table Search Procedures:
Methodology and Practical Guidelines [0.0]
機械学習技術の拡張が、このようなスピードアップにどのような貢献をできるかを調査する。
我々は、CPUおよびGPUコンピューティングの両方を考慮して、後者が前者に対して利益を上げることができるシナリオを特徴づける。
実際、ここで提案した学習表検索手順を自然に補完するアルゴリズム的パラダイムを定式化し、既知の学習表検索手順の大部分を、単純な線形回帰を近似した「学習フェーズ」を持つものとして特徴付ける。
論文 参考訳（メタデータ） (2020-07-20T16:26:54Z) - Hands-off Model Integration in Spatial Index Structures [8.710716183434918]
本稿では,軽量機械学習モデルを用いて空間インデックスのクエリを高速化する機会について検討する。
我々は、R木において、おそらく最も広く使われている空間指標である、それと類似した手法を使うことの可能性を探ることによって、そうする。
分析で示すように、クエリの実行時間を最大60%削減でき、同時にインデックスのメモリフットプリントを90%以上削減できる。
論文 参考訳（メタデータ） (2020-06-29T22:05:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。