論文の概要: ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering
using Nearest-Neighbor Chain
- arxiv url: http://arxiv.org/abs/2106.04727v1
- Date: Tue, 8 Jun 2021 23:13:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 14:52:21.312396
- Title: ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering
using Nearest-Neighbor Chain
- Title（参考訳）: parchain: near-neighbor chainを用いた並列階層型凝集クラスタリングフレームワーク
- Authors: Shangdi Yu, Yiqiu Wang, Yan Gu, Laxman Dhulipala, Julian Shun
- Abstract要約: 本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。
従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。
我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
- 参考スコア（独自算出の注目度）: 6.824747267214373
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the hierarchical clustering problem, where the goal is to
produce a dendrogram that represents clusters at varying scales of a data set.
We propose the ParChain framework for designing parallel hierarchical
agglomerative clustering (HAC) algorithms, and using the framework we obtain
novel parallel algorithms for the complete linkage, average linkage, and Ward's
linkage criteria. Compared to most previous parallel HAC algorithms, which
require quadratic memory, our new algorithms require only linear memory, and
are scalable to large data sets. ParChain is based on our parallelization of
the nearest-neighbor chain algorithm, and enables multiple clusters to be
merged on every round. We introduce two key optimizations that are critical for
efficiency: a range query optimization that reduces the number of distance
computations required when finding nearest neighbors of clusters, and a caching
optimization that stores a subset of previously computed distances, which are
likely to be reused.
Experimentally, we show that our highly-optimized implementations using 48
cores with two-way hyper-threading achieve 5.8--110.1x speedup over
state-of-the-art parallel HAC algorithms and achieve 13.75--54.23x
self-relative speedup. Compared to state-of-the-art algorithms, our algorithms
require up to 237.3x less space. Our algorithms are able to scale to data set
sizes with tens of millions of points, which existing algorithms are not able
to handle.
- Abstract（参考訳）: 本稿では,データセットの様々なスケールのクラスタを表すデンドログラムを作成することを目標とする階層的クラスタリング問題について検討する。
本稿では,並列階層型凝集クラスタリング(hac)アルゴリズムを設計するためのparchainフレームワークを提案する。
2次メモリを必要とする従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリのみを必要とし、大規模データセットにスケーラブルである。
ParChainは、最も近い隣り合う連鎖アルゴリズムの並列化に基づいており、ラウンド毎に複数のクラスタをマージすることができる。
提案手法では, クラスタ近傍のクラスタの探索に要する距離計算量を削減するレンジクエリ最適化と, 再利用される可能性のある計算済み距離のサブセットを格納するキャッシュ最適化という, 効率の面で重要な2つの最適化を導入する。
実験により、48コアと2方向ハイパースレッディングを用いた高最適化実装は、最先端の並列HACアルゴリズムよりも5.8-110.1xの高速化を実現し、13.75-54.23xの自己相対的高速化を実現した。
最先端のアルゴリズムと比較して、我々のアルゴリズムは最大237.3倍のスペースを必要とする。
我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
関連論文リスト
- Parallelization of the K-Means Algorithm with Applications to Big Data Clustering [0.23020018305241333]
LLoydのアルゴリズムを使ったK-Meansクラスタリングは、与えられたデータセットをKの異なるクラスタに分割する反復的なアプローチである。
このプロジェクトでは2つの異なるアプローチを比較します。
論文 参考訳（メタデータ） (2024-05-20T14:18:36Z) - PECANN: Parallel Efficient Clustering with Graph-Based Approximate
Nearest Neighbor Search [8.15681999722805]
本稿では, 点集合の密度に基づくクラスタリングについて検討する。
密度ピークの異なる変種を単一のフレームワークPECANNに統合する。
PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
論文 参考訳（メタデータ） (2023-12-06T22:43:50Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Breaking 3-Factor Approximation for Correlation Clustering in
Polylogarithmic Rounds [0.23633885460047763]
相関クラスタリング問題に対する並列アルゴリズムについて検討する。
目標は、エンティティをクラスタに分割し、ラベルとの相違を最小限にすることである。
現在、全ての効率的な並列アルゴリズムは、近似比が少なくとも3である。
3 より優れた近似比を実現するための最初の多元対数アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-13T12:32:49Z) - Efficient Approximate Kernel Based Spike Sequence Classification [56.2938724367661]
SVMのような機械学習モデルは、シーケンスのペア間の距離/相似性の定義を必要とする。
厳密な手法により分類性能は向上するが、計算コストが高い。
本稿では,その予測性能を向上させるために,近似カーネルの性能を改善する一連の方法を提案する。
論文 参考訳（メタデータ） (2022-09-11T22:44:19Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - A density peaks clustering algorithm with sparse search and K-d tree [16.141611031128427]
この問題を解決するために,スパース探索とK-d木を用いた密度ピーククラスタリングアルゴリズムを開発した。
分散特性が異なるデータセット上で、他の5つの典型的なクラスタリングアルゴリズムと比較して実験を行う。
論文 参考訳（メタデータ） (2022-03-02T09:29:40Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - 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) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。