論文の概要: Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A
Comparative Analysis
- arxiv url: http://arxiv.org/abs/2305.04359v1
- Date: Sun, 7 May 2023 19:28:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-09 16:12:15.950554
- Title: Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A
Comparative Analysis
- Title（参考訳）: グラフベースのANNSアルゴリズムを数十億規模のデータセットにスケールする:比較分析
- Authors: Magdalen Dobson, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan
Gu, Harsha Vardhan Simhadri, Yihan Sun
- Abstract要約: 現実世界のアプリケーションには、数十億ポイントのスケールで動作するアルゴリズムが必要です。
既存のANNSアルゴリズムの評価は、通常、1秒あたりのクエリの測定と最適化に重点を置いている。
本稿では,ANNSアルゴリズムのスケーラビリティを10億規模のデータセットに再定義する原理的尺度を提案する。
- 参考スコア（独自算出の注目度）: 9.171421711190932
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Algorithms for approximate nearest-neighbor search (ANNS) have been the topic
of significant recent interest in the research community. However, evaluations
of such algorithms are usually restricted to a small number of datasets with
millions or tens of millions of points, whereas real-world applications require
algorithms that work on the scale of billions of points. Furthermore, existing
evaluations of ANNS algorithms are typically heavily focused on measuring and
optimizing for queries-per second (QPS) at a given accuracy, which can be
hardware-dependent and ignores important metrics such as build time.
In this paper, we propose a set of principled measures for evaluating ANNS
algorithms which refocuses on their scalability to billion-size datasets. These
measures include ability to be efficiently parallelized, build times, and
scaling relationships as dataset size increases. We also expand on the QPS
measure with machine-agnostic measures such as the number of distance
computations per query, and we evaluate ANNS data structures on their accuracy
in more demanding settings required in modern applications, such as evaluating
range queries and running on out-of-distribution data. We optimize four
graph-based algorithms for the billion-scale setting, and in the process
provide a general framework for making many incremental ANNS graph algorithms
lock-free. We use our framework to evaluate the aforementioned graph-based ANNS
algorithms as well as two alternative approaches.
- Abstract（参考訳）: ほぼ近接探索(ANNS)のためのアルゴリズムは、最近研究コミュニティにおいて重要な関心を集めている。
しかし、そのようなアルゴリズムの評価は通常、数百万から数千万のポイントを持つ少数のデータセットに限定されるが、現実世界のアプリケーションは数十億ポイントのスケールで動作するアルゴリズムを必要とする。
さらに、ANNSアルゴリズムの既存の評価は、通常、所定の精度でクエリ毎秒(QPS)の測定と最適化に重点を置いている。
本稿では,10億規模のデータセットへの拡張性に再焦点をあてた anns アルゴリズムの評価手法を提案する。
これらの測定には、効率的な並列化、ビルド時間、データセットサイズの増加に伴う関係のスケーリングなどが含まれる。
また,クエリ毎の距離計算数などのマシン非依存の尺度でQPS尺度を拡張し,レンジクエリの評価やアウト・オブ・ディストリビューションデータの実行など,最新のアプリケーションで要求されるより要求の高い設定において,ANNSデータ構造を精度良く評価する。
数十億のスケール設定のために4つのグラフベースのアルゴリズムを最適化し、その過程で、インクリメンタルなANNSグラフアルゴリズムをロックフリーにするための一般的なフレームワークを提供する。
我々は、前述のグラフベースのANNSアルゴリズムと2つの代替アプローチを評価するためにフレームワークを使用します。
関連論文リスト
- Comparing Personalized Relevance Algorithms for Directed Graphs [0.34952465649465553]
我々は、有向グラフが与えられた場合、与えられたクエリノードに関連する最も関連性の高いノードを識別できる対話型Webプラットフォームを提案する。
Wikipedia、Twitter、Amazonから50のプレロードデータセットと7つのアルゴリズムを提供しています。
我々のツールは、データ内の隠れた関係を明らかにするのに役立ち、グラフ解析アルゴリズムのレパートリーに価値ある追加となる。
論文 参考訳（メタデータ） (2024-05-03T17:24:08Z) - A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-12-17T04:41:07Z) - PECANN: Parallel Efficient Clustering with Graph-Based Approximate
Nearest Neighbor Search [8.15681999722805]
本稿では, 点集合の密度に基づくクラスタリングについて検討する。
密度ピークの異なる変種を単一のフレームワークPECANNに統合する。
PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
論文 参考訳（メタデータ） (2023-12-06T22:43:50Z) - Learning the hub graphical Lasso model with the structured sparsity via
an efficient algorithm [1.0923877073891446]
ハブグラフィカルモデルを推定する二相アルゴリズムを提案する。
提案アルゴリズムはまず,乗算器の2つの交互方向法を用いてよい初期点を生成する。
その後、半滑らかなニュートン(SSN)ベースの拡張ラグランジアン法(ALM)を温め、実用的なタスクに十分正確な解を計算する。
論文 参考訳（メタデータ） (2023-08-17T08:24:28Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Accelerating ERM for data-driven algorithm design using output-sensitive techniques [26.32088674030797]
データ駆動型アルゴリズム設計のための効率的な学習アルゴリズムを開発するための技術について研究する。
提案手法は,超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムである。
本稿では、価格問題、リンクベースのクラスタリング、動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提供することにより、我々の技術を説明する。
論文 参考訳（メタデータ） (2022-04-07T17:27:18Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。