論文の概要: A Learned Index for Exact Similarity Search in Metric Spaces

• arxiv url: http://arxiv.org/abs/2204.10028v1
• Date: Thu, 21 Apr 2022 11:24:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-22 14:53:19.125494
• Title: A Learned Index for Exact Similarity Search in Metric Spaces
• Title（参考訳）: 距離空間における完全類似性探索のための学習インデックス
• Authors: Yao Tian, Tingyun Yan, Xi Zhao, Kai Huang, Xiaofang Zhou
• Abstract要約: LIMSは、学習したインデックスを構築するために、データクラスタリングとピボットベースのデータ変換技術を使用することが提案されている。 機械学習モデルはディスク上の各データレコードの位置を近似するために開発された。 実世界のデータセットと合成データセットに関する大規模な実験は、従来の指標と比較してLIMSの優位性を示している。
• 参考スコア（独自算出の注目度）: 25.330353637669386
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Indexing is an effective way to support efficient query processing in large databases. Recently the concept of learned index has been explored actively to replace or supplement traditional index structures with machine learning models to reduce storage and search costs. However, accurate and efficient similarity query processing in high-dimensional metric spaces remains to be an open challenge. In this paper, a novel indexing approach called LIMS is proposed to use data clustering and pivot-based data transformation techniques to build learned indexes for efficient similarity query processing in metric spaces. The underlying data is partitioned into clusters such that each cluster follows a relatively uniform data distribution. Data redistribution is achieved by utilizing a small number of pivots for each cluster. Similar data are mapped into compact regions and the mapped values are totally ordinal. Machine learning models are developed to approximate the position of each data record on the disk. Efficient algorithms are designed for processing range queries and nearest neighbor queries based on LIMS, and for index maintenance with dynamic updates. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of LIMS compared with traditional indexes and state-of-the-art learned indexes.
• Abstract（参考訳）: インデックス化は、大規模なデータベースで効率的なクエリ処理をサポートする効果的な方法である。 近年、学習インデックスの概念は、従来のインデックス構造を機械学習モデルに置き換え、補うことで、ストレージと検索コストを削減するために積極的に研究されている。 しかし、高次元距離空間における高精度で効率的な類似性クエリ処理は未解決の課題である。 本稿では,データクラスタリングとピボットベースのデータ変換技術を用いて,距離空間における類似性クエリ処理を効率的に行うための学習インデックスを構築するために,LIMSと呼ばれる新しいインデックス手法を提案する。 基礎となるデータはクラスタに分割され、各クラスタは比較的均一なデータ分布に従う。 データの再分配は、各クラスタに少数のピボットを使用することで実現される。 同様のデータはコンパクトな領域にマッピングされ、マッピングされた値は完全順序数である。 ディスク上の各データレコードの位置を近似する機械学習モデルを開発した。 効率的なアルゴリズムは、LIMSに基づく範囲クエリと最も近い隣のクエリを処理し、動的更新を伴うインデックスメンテナンスのために設計されている。 実世界および合成データセットに関する広範な実験は、limが従来のインデックスや最先端の学習インデックスよりも優れていることを示している。

関連論文リスト

• 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)
• Faster Learned Sparse Retrieval with Block-Max Pruning [11.080810272211906]
  本稿では,学習されたスパース検索環境に出現するインデックスに適した,革新的な動的プルーニング戦略であるBlock-Max Pruning(BMP)を紹介する。 BMPは既存の動的プルーニング戦略を大幅に上回り、安全な検索コンテキストにおいて非並列効率を提供する。
  論文  参考訳（メタデータ） (2024-05-02T09:26:30Z)
• 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)
• WISK: A Workload-aware Learned Index for Spatial Keyword Queries [46.96314606580924]
  本稿では,空間的キーワードクエリの学習指標であるWISKを提案する。 We show that WISK achieve up to 8x speedup in querying time with comparable storage overhead。
  論文  参考訳（メタデータ） (2023-02-28T03:45:25Z)
• End-to-End Learning to Index and Search in Large Output Spaces [95.16066833532396]
  Extreme Multi-label Classification (XMC) は現実世界の問題を解決するための一般的なフレームワークである。 本稿では,木系インデックスを特殊重み付きグラフベースインデックスに緩和する新しい手法を提案する。 ELIASは、数百万のラベルを持つ大規模極端分類ベンチマークで最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2022-10-16T01:34:17Z)
• A Pluggable Learned Index Method via Sampling and Gap Insertion [48.900186573181735]
  データベースインデックスは、データ検索を促進し、現実世界のシステムにおける幅広いアプリケーションに役立つ。 近年,隠れて有用なデータ分布を学習するために,learning indexという新しいインデックスが提案されている。 学習指標の学習効率と学習効率を高めるための2つの一般的なテクニックとプラグイン可能なテクニックを研究します。
  論文  参考訳（メタデータ） (2021-01-04T07:17:23Z)
• 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)
• Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads [29.223401893397714]
  我々は,既存の学習した多次元インデックスよりも最大6倍高速なクエリ性能と最大8倍のインデックスサイズを実現する綱見を紹介した。
  論文  参考訳（メタデータ） (2020-06-23T19:25:51Z)

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

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