論文の概要: Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering
- arxiv url: http://arxiv.org/abs/2104.01126v1
- Date: Fri, 2 Apr 2021 16:05:00 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-05 13:38:10.040019
- Title: Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering
- Title（参考訳）: ユークリッド最小スパンニングツリーと階層空間クラスタリングのための高速並列アルゴリズム
- Authors: Yiqiu Wang, Shangdi Yu, Yan Gu, Julian Shun
- Abstract要約: HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
- 参考スコア（独自算出の注目度）: 6.4805900740861
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents new parallel algorithms for generating Euclidean minimum
spanning trees and spatial clustering hierarchies (known as HDBSCAN$^*$). Our
approach is based on generating a well-separated pair decomposition followed by
using Kruskal's minimum spanning tree algorithm and bichromatic closest pair
computations. We introduce a new notion of well-separation to reduce the work
and space of our algorithm for HDBSCAN$^*$. We also present a parallel
approximate algorithm for OPTICS based on a recent sequential algorithm by Gan
and Tao. Finally, we give a new parallel divide-and-conquer algorithm for
computing the dendrogram and reachability plots, which are used in visualizing
clusters of different scale that arise for both EMST and HDBSCAN$^*$. We show
that our algorithms are theoretically efficient: they have work (number of
operations) matching their sequential counterparts, and polylogarithmic depth
(parallel time).
We implement our algorithms and propose a memory optimization that requires
only a subset of well-separated pairs to be computed and materialized, leading
to savings in both space (up to 10x) and time (up to 8x). Our experiments on
large real-world and synthetic data sets using a 48-core machine show that our
fastest algorithms outperform the best serial algorithms for the problems by
11.13--55.89x, and existing parallel algorithms by at least an order of
magnitude.
- Abstract（参考訳）: 本稿では,ユークリッド最小分散木と空間クラスタリング階層(HDBSCAN$^*$)を生成するための新しい並列アルゴリズムを提案する。
提案手法は, kruskal の最小スパンディングツリーアルゴリズムと双色最接近対計算を用いて, 分離されたペア分解を生成することに基づいている。
我々は、HDBSCAN$^*$に対して、アルゴリズムの作業量と空間を減らし、ウェルセパレーションという新しい概念を導入する。
また,gan と tao による最近の逐次アルゴリズムに基づく光学の並列近似アルゴリズムを提案する。
最後に, EMSTとHDBSCAN$^*$の両方で発生する異なるスケールのクラスタを可視化するために, デンドログラムと到達可能性プロットを計算するための新しい並列分割計算アルゴリズムを提案する。
提案アルゴリズムは, 逐次的処理量(演算数)と多対数深度(並列時間)とが一致し, 理論的に効率的であることを示す。
我々はアルゴリズムを実装し、計算と実現のために分離されたペアのサブセットのみを必要とするメモリ最適化を提案し、空間(最大10倍)と時間(最大8倍)の両方を節約する。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
関連論文リスト
- Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳（メタデータ） (2022-03-07T21:40:14Z) - Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer
Vision [6.574107319036238]
Hochbaum pseudoflowアルゴリズムは最速のシリアルアルゴリズムであり、Boykov-Kolmogorovアルゴリズムは最もメモリ効率が高い。
既存の min-cut/max-flow アルゴリズムは、大きな問題ではシリアルアルゴリズムを著しく上回るが、中小問題ではオーバーヘッドが増大する。
論文 参考訳（メタデータ） (2022-02-01T14:06:27Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。
我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。
最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-04T10:33:59Z) - ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering
using Nearest-Neighbor Chain [6.824747267214373]
本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。
従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。
我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
論文 参考訳（メタデータ） (2021-06-08T23:13:27Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。