論文の概要: COAX: Correlation-Aware Indexing on Multidimensional Data with Soft Functional Dependencies

• arxiv url: http://arxiv.org/abs/2006.16393v3
• Date: Tue, 2 Feb 2021 15:43:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-15 15:34:15.406537
• Title: COAX: Correlation-Aware Indexing on Multidimensional Data with Soft Functional Dependencies
• Title（参考訳）: COAX:ソフト関数依存型多次元データにおける相関認識インデックス
• Authors: Ali Hadian, Behzad Ghaffari, Taiyi Wang, Thomas Heinis
• Abstract要約: データセットの属性間の相関関係を学習する多次元データのための学習指標であるCOAXを提案する。 実験により,データ中の関連属性を予測することにより,クエリ実行時間を短縮し,インデックスのメモリオーバーヘッドを低減することができることがわかった。
• 参考スコア（独自算出の注目度）: 3.670422696827525
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work proposed learned index structures, which learn the distribution of the underlying dataset to improve performance. The initial work on learned indexes has shown that by learning the cumulative distribution function of the data, index structures such as the B-Tree can improve their performance by one order of magnitude while having a smaller memory footprint. In this paper, we present COAX, a learned index for multidimensional data that, instead of learning the distribution of keys, learns the correlations between attributes of the dataset. Our approach is driven by the observation that in many datasets, values of two (or multiple) attributes are correlated. COAX exploits these correlations to reduce the dimensionality of the datasets. More precisely, we learn how to infer one (or multiple) attribute $C_d$ from the remaining attributes and hence no longer need to index attribute $C_d$. This reduces the dimensionality and hence makes the index smaller and more efficient. We theoretically investigate the effectiveness of the proposed technique based on the predictability of the FD attributes. We further show experimentally that by predicting correlated attributes in the data, we can improve the query execution time and reduce the memory overhead of the index. In our experiments, we reduce the execution time by 25% while reducing the memory footprint of the index by four orders of magnitude.
• Abstract（参考訳）: 最近の研究は、パフォーマンスを改善するために基礎となるデータセットの分布を学習する学習インデックス構造を提案している。 学習されたインデックスに関する最初の研究は、データの累積分布関数を学習することで、b木のようなインデックス構造がメモリフットプリントを小さくしながら、その性能を1桁改善できることを示した。 本稿では,鍵の分布を学習する代わりに,データセットの属性間の相関関係を学習する多次元データのための学習指標であるCOAXを提案する。 我々のアプローチは、多くのデータセットにおいて、2つの(または複数の)属性の値が相関しているという観測によって導かれる。 COAXはこれらの相関を利用してデータセットの次元を減少させる。 より正確には、ある(または複数の)属性を残りの属性から$c_d$を推測する方法を学び、したがって$c_d$をインデックスする必要がない。 これにより次元が小さくなり、インデックスはより小さくより効率的になる。 提案手法の有効性をFD属性の予測可能性に基づいて理論的に検討する。 さらに,データ中の関連属性を予測することにより,クエリ実行時間を短縮し,インデックスのメモリオーバーヘッドを低減できることを実験的に示す。 実験では,インデックスのメモリフットプリントを4桁に減らしながら,実行時間を25%削減した。

関連論文リスト

• 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)
• Compact Neural Graphics Primitives with Learned Hash Probing [100.07267906666293]
  学習したプローブを持つハッシュテーブルにはデメリットはなく,その結果,サイズと速度の組合せが好適であることを示す。 推論は、トレーニングが1.2-2.6倍遅い間、同じ品質で未処理のハッシュテーブルよりも高速である。
  論文  参考訳（メタデータ） (2023-12-28T18:58:45Z)
• OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries [8.950168559003993]
  Approximate Nearest Neighbor Search (ANNS)の最先端アルゴリズムは、インデックスデータ分布にオーバーフィットすることで、データに依存したインデックスを構築する。 OOD-DiskANNはOODクエリのスペーリングサンプル(インデックスセットサイズの1%)を使用し、同じメモリフットプリントのSoTAアルゴリズムに対して、平均クエリレイテンシを最大40%改善する。
  論文  参考訳（メタデータ） (2022-10-22T21:22:50Z)
• NFL: Robust Learned Index via Distribution Transformation [14.812854942243503]
  本稿では、学習インデックスを構築する前に、鍵にテキスト分布変換を適用することで近似問題に取り組む。 2段階の正規化フローベース学習インデックスフレームワーク (NFL) が提案され、最初に元の複雑な鍵分布をほぼ一様に変換し、次に変換された鍵を利用する学習インデックスを構築する。 変換キーの特性に基づいて、ロバストなアフターフロー学習指標(AFLI)を提案する。
  論文  参考訳（メタデータ） (2022-05-24T06:03:19Z)
• A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
  LIMSは、学習したインデックスを構築するために、データクラスタリングとピボットベースのデータ変換技術を使用することが提案されている。 機械学習モデルはディスク上の各データレコードの位置を近似するために開発された。 実世界のデータセットと合成データセットに関する大規模な実験は、従来の指標と比較してLIMSの優位性を示している。
  論文  参考訳（メタデータ） (2022-04-21T11:24:55Z)
• Micro-architectural Analysis of a Learned Index [0.0]
  ALEXはツリーベースのインメモリインデックス構造であり、機械学習モデルの階層構造で構成されている。 その結果、ALEXはストールを少なくし、異なるワークロードにまたがるインストラクションあたりのサイクル値が低いことがわかった。 一方、ALEXのアウト・オブ・バウンド・インサートを扱うのに必要な命令の量は、リクエスト毎の命令を著しく増加させる(10X)。
  論文  参考訳（メタデータ） (2021-09-17T12:13:06Z)
• How to distribute data across tasks for meta-learning? [59.608652082495624]
  タスクごとのデータポイントの最適な数は予算に依存しますが、それは大きな予算のためのユニークな一定の値に収束します。 この結果から,データ収集の簡便かつ効率的な手順が示唆された。
  論文  参考訳（メタデータ） (2021-03-15T15:38:47Z)
• 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)
• RadixSpline: A Single-Pass Learned Index [84.84747738666263]
  RadixSpline(RS)は、データに1回のパスで構築できる学習インデックスです。 RSは2つのパラメータしか持たないにもかかわらず、すべてのデータセットで競合的な結果を達成する。
  論文  参考訳（メタデータ） (2020-04-30T01:56:54Z)
• New advances in enumerative biclustering algorithms with online partitioning [80.22629846165306]
  さらに、数値データセットの列に定数値を持つ最大二クラスタの効率的で完全で正しい非冗長列挙を実現できる二クラスタリングアルゴリズムであるRIn-Close_CVCを拡張した。 改良されたアルゴリズムはRIn-Close_CVC3と呼ばれ、RIn-Close_CVCの魅力的な特性を保ちます。
  論文  参考訳（メタデータ） (2020-03-07T14:54:26Z)

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

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