論文の概要: ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms

• arxiv url: http://arxiv.org/abs/2305.04359v2
• Date: Thu, 8 Feb 2024 17:00:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-10 03:17:03.891946
• Title: ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms
• Title（参考訳）: ParlayANN: スケーラブルで決定論的並列グラフに基づく近似近傍探索アルゴリズム
• Authors: Magdalen Dobson Manohar, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, Yihan Sun
• Abstract要約: 本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。 我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
• 参考スコア（独自算出の注目度）: 5.478671305092084
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximate nearest-neighbor search (ANNS) algorithms are a key part of the modern deep learning stack due to enabling efficient similarity search over high-dimensional vector space representations (i.e., embeddings) of data. Among various ANNS algorithms, graph-based algorithms are known to achieve the best throughput-recall tradeoffs. Despite the large scale of modern ANNS datasets, existing parallel graph based implementations suffer from significant challenges to scale to large datasets due to heavy use of locks and other sequential bottlenecks, which 1) prevents them from efficiently scaling to a large number of processors, and 2) results in nondeterminism that is undesirable in certain applications. In this paper, we introduce ParlayANN, a library of deterministic and parallel graph-based approximate nearest neighbor search algorithms, along with a set of useful tools for developing such algorithms. In this library, we develop novel parallel implementations for four state-of-the-art graph-based ANNS algorithms that scale to billion-scale datasets. Our algorithms are deterministic and achieve high scalability across a diverse set of challenging datasets. In addition to the new algorithmic ideas, we also conduct a detailed experimental study of our new algorithms as well as two existing non-graph approaches. Our experimental results both validate the effectiveness of our new techniques, and lead to a comprehensive comparison among ANNS algorithms on large scale datasets with a list of interesting findings.
• Abstract（参考訳）: 近似近傍探索(ANNS)アルゴリズムは、データの高次元ベクトル空間表現(つまり埋め込み)の効率的な類似性探索を可能にするため、現代のディープラーニングスタックの重要な部分である。 様々なANNSアルゴリズムの中で、グラフベースのアルゴリズムは最高のスループット-リコールトレードオフを達成することが知られている。 現代のannsデータセットは大規模であるにも関わらず、既存の並列グラフベースの実装は、ロックやその他のシーケンシャルなボトルネックを多用するため、大規模なデータセットに拡張する上で大きな課題を抱えている。 1)多数のプロセッサへの効率的なスケーリングを防止し、 2) 特定の応用では望ましくない非決定論が生じる。 本稿では,決定論的および並列グラフに基づく近似近辺探索アルゴリズムのライブラリparlayannと,それらのアルゴリズムを開発するための有用なツールセットを提案する。 このライブラリでは,数十億のデータセットにスケールする4つの最先端グラフベースANNSアルゴリズムの並列実装を開発する。 我々のアルゴリズムは決定論的であり、多様な挑戦的なデータセットに対して高いスケーラビリティを実現する。 新しいアルゴリズムのアイデアに加えて、我々は新しいアルゴリズムと既存の2つの非グラフアプローチの詳細な実験的研究も行っている。 実験結果は,新しい手法の有効性を検証し,大規模データセットにおける anns アルゴリズムの包括的比較を行った結果,興味深い結果が得られた。

関連論文リスト

• 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)

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

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