論文の概要: The Case for Learned Spatial Indexes
- arxiv url: http://arxiv.org/abs/2008.10349v1
- Date: Mon, 24 Aug 2020 12:09:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-25 12:35:03.471371
- Title: The Case for Learned Spatial Indexes
- Title(参考訳): 学習した空間指標の事例
- Authors: Varun Pandey, Alexander van Renen, Andreas Kipf, Ibrahim Sabek, Jialin
Ding, Alfons Kemper
- Abstract要約: 我々は、空間範囲の問合せに答えるために、最先端の学習した多次元インデックス構造(すなわちFlood)から提案した手法を用いる。
i) パーティション内の機械学習検索は、1次元でフィルタリングを使用する場合の2進探索よりも11.79%速く、39.51%高速であることを示す。
また、2次元でフィルタする最も近い競合相手の1.23倍から1.83倍の速さで機械学習インデックスを精査する。
- 参考スコア(独自算出の注目度): 62.88514422115702
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spatial data is ubiquitous. Massive amounts of data are generated every day
from billions of GPS-enabled devices such as cell phones, cars, sensors, and
various consumer-based applications such as Uber, Tinder, location-tagged posts
in Facebook, Twitter, Instagram, etc. This exponential growth in spatial data
has led the research community to focus on building systems and applications
that can process spatial data efficiently. In the meantime, recent research has
introduced learned index structures. In this work, we use techniques proposed
from a state-of-the art learned multi-dimensional index structure (namely,
Flood) and apply them to five classical multi-dimensional indexes to be able to
answer spatial range queries. By tuning each partitioning technique for optimal
performance, we show that (i) machine learned search within a partition is
faster by 11.79\% to 39.51\% than binary search when using filtering on one
dimension, (ii) the bottleneck for tree structures is index lookup, which could
potentially be improved by linearizing the indexed partitions (iii) filtering
on one dimension and refining using machine learned indexes is 1.23x to 1.83x
times faster than closest competitor which filters on two dimensions, and (iv)
learned indexes can have a significant impact on the performance of low
selectivity queries while being less effective under higher selectivities.
- Abstract(参考訳): 空間データはユビキタスである。
大量のデータは、携帯電話、車、センサー、そしてUber、Tinder、Facebook、Twitter、Instagramなどのさまざまな消費者向けアプリケーションなど、何十億ものGPS対応デバイスから毎日生成される。
この空間データの増加により、研究コミュニティは空間データを効率的に処理できるシステムやアプリケーションの構築に注力するようになった。
一方,最近の研究は学習指標構造を導入している。
本研究では,最先端の学習した多次元インデックス構造(すなわちFlood)から提案した手法を用いて,空間範囲の問合せに応答できる5つの古典的多次元インデックスに適用する。
各パーティショニングテクニックを最適性能に調整することにより、そのことを示す。
(i)1次元のフィルタリングを使用する場合、分割内の機械学習検索は、バイナリ検索よりも11.79\%速く39.51\%である。
(ii)木構造におけるボトルネックはインデックス検索であり、インデックス分割を線形化することで改善される可能性がある。
(iii)1次元のフィルタリングと機械学習インデックスによる精錬は2次元のフィルタと最も近い競争相手の1.23倍から1.83倍高速である。
(4) 学習指標は, 高い選択性の下では効率が悪く, 低い選択性クエリの性能に大きな影響を及ぼす可能性がある。
関連論文リスト
- Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes? [62.57689536630933]
本稿では,オープンソースのLucene検索ライブラリを用いたBEIRデータセットの実験結果について述べる。
本研究は,高密度かつ疎密なレトリバーの設計空間を理解するための,今日の検索実践者へのガイダンスを提供する。
論文 参考訳(メタデータ) (2024-09-10T12:46:23Z) - 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) - Semi-Parametric Retrieval via Binary Token Index [71.78109794895065]
Semi-parametric Vocabulary Disentangled Retrieval (SVDR) は、新しい半パラメトリック検索フレームワークである。
既存のニューラル検索手法に似た、高い有効性のための埋め込みベースのインデックスと、従来の用語ベースの検索に似た、迅速かつ費用対効果の高いセットアップを可能にするバイナリトークンインデックスの2つのタイプをサポートする。
埋め込みベースインデックスを使用する場合の高密度検索器DPRよりも3%高いトップ1検索精度と、バイナリトークンインデックスを使用する場合のBM25よりも9%高いトップ1検索精度を実現する。
論文 参考訳(メタデータ) (2024-05-03T08:34:13Z) - 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) - A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
LIMSは、学習したインデックスを構築するために、データクラスタリングとピボットベースのデータ変換技術を使用することが提案されている。
機械学習モデルはディスク上の各データレコードの位置を近似するために開発された。
実世界のデータセットと合成データセットに関する大規模な実験は、従来の指標と比較してLIMSの優位性を示している。
論文 参考訳(メタデータ) (2022-04-21T11:24:55Z) - Towards Improving the Consistency, Efficiency, and Flexibility of
Differentiable Neural Architecture Search [84.4140192638394]
最も微分可能なニューラルアーキテクチャ探索法は、探索用のスーパーネットを構築し、そのサブグラフとしてターゲットネットを導出する。
本稿では,エンジンセルとトランジットセルからなるEnTranNASを紹介する。
また,検索処理の高速化を図るため,メモリや計算コストの削減も図っている。
論文 参考訳(メタデータ) (2021-01-27T12:16:47Z) - A Pluggable Learned Index Method via Sampling and Gap Insertion [48.900186573181735]
データベースインデックスは、データ検索を促進し、現実世界のシステムにおける幅広いアプリケーションに役立つ。
近年,隠れて有用なデータ分布を学習するために,learning indexという新しいインデックスが提案されている。
学習指標の学習効率と学習効率を高めるための2つの一般的なテクニックとプラグイン可能なテクニックを研究します。
論文 参考訳(メタデータ) (2021-01-04T07:17:23Z) - Hands-off Model Integration in Spatial Index Structures [8.710716183434918]
本稿では,軽量機械学習モデルを用いて空間インデックスのクエリを高速化する機会について検討する。
我々は、R木において、おそらく最も広く使われている空間指標である、それと類似した手法を使うことの可能性を探ることによって、そうする。
分析で示すように、クエリの実行時間を最大60%削減でき、同時にインデックスのメモリフットプリントを90%以上削減できる。
論文 参考訳(メタデータ) (2020-06-29T22:05:28Z) - Tsunami: A Learned Multi-dimensional Index for Correlated Data and
Skewed Workloads [29.223401893397714]
我々は,既存の学習した多次元インデックスよりも最大6倍高速なクエリ性能と最大8倍のインデックスサイズを実現する綱見を紹介した。
論文 参考訳(メタデータ) (2020-06-23T19:25:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。