論文の概要: Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigation
- arxiv url: http://arxiv.org/abs/2404.19284v4
- Date: Wed, 02 Oct 2024 07:30:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-03 15:16:54.940483
- Title: Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigation
- Title（参考訳）: 動的データセットの近似近傍探索に関する研究
- Authors: Ben Harwood, Amir Dezfouli, Iadine Chades, Conrad Sanderson,
- Abstract要約: 近似k-Nearest Neighbour (ANN) 法は情報マイニングや大規模高次元データセットでの機械学習支援によく用いられる。
静的なデータセットを持つアプリケーションでは、ランタイム制約とデータセットプロパティを使用して、適切な操作特性を持つANNメソッドを経験的に選択することができる。
従来の評価手法は、インデックス構造を更新する際の計算コストや、インデックス更新の率とサイズを考慮していない。
- 参考スコア（独自算出の注目度）: 20.409659920455955
- License:
- Abstract: Approximate k-Nearest Neighbour (ANN) methods are often used for mining information and aiding machine learning on large scale high-dimensional datasets. ANN methods typically differ in the index structure used for accelerating searches, resulting in various recall/runtime trade-off points. For applications with static datasets, runtime constraints and dataset properties can be used to empirically select an ANN method with suitable operating characteristics. However, for applications with dynamic datasets, which are subject to frequent online changes (like addition of new samples), there is currently no consensus as to which ANN methods are most suitable. Traditional evaluation approaches do not consider the computational costs of updating the index structure, as well as the rate and size of index updates. To address this, we empirically evaluate 5 popular ANN methods on two main applications (online data collection and online feature learning) while taking into account these considerations. Two dynamic datasets are used, derived from the SIFT1M dataset with 1 million samples and the DEEP1B dataset with 1 billion samples. The results indicate that the often used k-d trees method is not suitable on dynamic datasets as it is slower than a straightforward baseline exhaustive search method. For online data collection, the Hierarchical Navigable Small World Graphs method achieves a consistent speedup over baseline across a wide range of recall rates. For online feature learning, the Scalable Nearest Neighbours method is faster than baseline for recall rates below 75%.
- Abstract（参考訳）: 近似k-Nearest Neighbour (ANN) 法は情報マイニングや大規模高次元データセットでの機械学習支援によく用いられる。
ANN法は通常、検索の高速化に使用されるインデックス構造が異なるため、様々なリコール/実行時のトレードオフ点が生じる。
静的なデータセットを持つアプリケーションでは、ランタイム制約とデータセットプロパティを使用して、適切な操作特性を持つANNメソッドを経験的に選択することができる。
しかし、オンラインの頻繁な変更(新しいサンプルの追加など)の対象となる動的データセットを持つアプリケーションでは、どのANNメソッドが最も適しているかについては、現時点では合意が得られていない。
従来の評価手法は、インデックス構造を更新する際の計算コストや、インデックス更新の率とサイズを考慮していない。
これを解決するために、これらの考慮を考慮しつつ、2つの主要なアプリケーション(オンラインデータ収集とオンライン特徴学習)で5つの人気のあるANN手法を実証的に評価する。
100万のサンプルを持つSIFT1Mデータセットと10億のサンプルを持つDEEP1Bデータセットから派生した2つの動的データセットが使用されている。
その結果,k-d木法は,単純なベースライン探索法よりも遅いため,動的データセットには適さないことがわかった。
オンラインデータ収集において、階層ナビゲート可能な小型世界グラフ法は、幅広いリコールレートでベースラインを一貫したスピードアップを達成する。
オンライン機能学習において、スケーラブルなNearest Neighboursメソッドは75%未満のリコール率のベースラインよりも高速である。
関連論文リスト
- Inferring Neural Signed Distance Functions by Overfitting on Single Noisy Point Clouds through Finetuning Data-Driven based Priors [53.6277160912059]
本稿では,データ駆動型およびオーバーフィット型手法のプロースを推進し,より一般化し,高速な推論を行い,より高精度なニューラルネットワークSDFを学習する手法を提案する。
そこで本研究では,距離管理やクリーンポイントクラウド,あるいは点正規化を伴わずに,データ駆動型プリエントを微調整できる新しい統計的推論アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-25T16:48:44Z) - No learning rates needed: Introducing SALSA -- Stable Armijo Line Search Adaptation [4.45108516823267]
我々は,現在最先端のライン探索手法の問題点を特定し,改良を提案し,その妥当性を厳格に評価する。
我々はこれらの手法を従来よりも桁違いに複雑なデータ領域で評価する。
私たちの作業はPythonパッケージで公開されており、シンプルなPytorchを提供しています。
論文 参考訳（メタデータ） (2024-07-30T08:47:02Z) - CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion [8.036012885171166]
我々は、動的データ取り込みを伴う連続近似Nearest Neighbor Searchに適したベンチマークであるCANDYを紹介する。
CANDYは幅広いAKNNアルゴリズムを包括的に評価し、機械学習駆動推論のような高度な最適化を統合する。
多様なデータセットに対する評価では、より単純なAKNNベースラインが、リコールやレイテンシの点で、より複雑な選択肢を上回ることが示されている。
論文 参考訳（メタデータ） (2024-06-28T04:46:11Z) - Minimally Supervised Learning using Topological Projections in
Self-Organizing Maps [55.31182147885694]
自己組織化マップ(SOM)におけるトポロジカルプロジェクションに基づく半教師付き学習手法を提案する。
提案手法は,まずラベル付きデータ上でSOMを訓練し,最小限のラベル付きデータポイントをキーベストマッチングユニット(BMU)に割り当てる。
提案した最小教師付きモデルが従来の回帰手法を大幅に上回ることを示す。
論文 参考訳（メタデータ） (2024-01-12T22:51:48Z) - Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls
and New Benchmarking [66.83273589348758]
リンク予測は、グラフのエッジの一部のみに基づいて、目に見えないエッジが存在するかどうかを予測しようとする。
近年,この課題にグラフニューラルネットワーク(GNN)を活用すべく,一連の手法が導入されている。
これらの新しいモデルの有効性をよりよく評価するために、新しい多様なデータセットも作成されている。
論文 参考訳（メタデータ） (2023-06-18T01:58:59Z) - Learning with Neighbor Consistency for Noisy Labels [69.83857578836769]
特徴空間におけるトレーニング例間の類似性を利用した雑音ラベルから学習する手法を提案する。
合成(CIFAR-10, CIFAR-100)とリアル(mini-WebVision, Clothing1M, mini-ImageNet-Red)の両方のノイズを評価するデータセットの評価を行った。
論文 参考訳（メタデータ） (2022-02-04T15:46:27Z) - Fast Single-Core K-Nearest Neighbor Graph Computation [0.0]
本論文では,Wei Dongらによるランタイム"NN-Descent"アルゴリズムを最適化したC実装を提案する。
低次元および高次元データセットの性能を改善するための様々な実装最適化について説明する。
l2距離メートル法の制限により、高次元データセットの性能を大幅に向上させるブロックされた距離評価が利用可能となる。
論文 参考訳（メタデータ） (2021-12-13T13:16:30Z) - Efficient Nearest Neighbor Language Models [114.40866461741795]
非パラメトリックニューラルネットワークモデル(NLM)は、外部データストアを用いてテキストの予測分布を学習する。
比較性能を維持しながら、推論速度の最大6倍の高速化を実現する方法を示す。
論文 参考訳（メタデータ） (2021-09-09T12:32:28Z) - Deep Retrieval: Learning A Retrievable Structure for Large-Scale
Recommendations [21.68175843347951]
本稿では,ユーザとイテムのインタラクションデータを用いて,検索可能な構造を直接学習するために,Deep Retrieval(DR)を提案する。
DRは、産業レコメンデーションシステムのために数億のアイテムをスケールで展開した最初の非ANNアルゴリズムの1つである。
論文 参考訳（メタデータ） (2020-07-12T06:23:51Z) - DC-NAS: Divide-and-Conquer Neural Architecture Search [108.57785531758076]
本稿では,ディープ・ニューラル・アーキテクチャーを効果的かつ効率的に探索するためのディバイド・アンド・コンカ(DC)手法を提案する。
ImageNetデータセットで75.1%の精度を達成しており、これは同じ検索空間を使った最先端の手法よりも高い。
論文 参考訳（メタデータ） (2020-05-29T09:02:16Z) - A Practical Index Structure Supporting Fr\'echet Proximity Queries Among
Trajectories [1.9335262420787858]
我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。
計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。
本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
論文 参考訳（メタデータ） (2020-05-28T04:12:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。