論文の概要: PECANN: Parallel Efficient Clustering with Graph-Based Approximate
Nearest Neighbor Search
- arxiv url: http://arxiv.org/abs/2312.03940v2
- Date: Wed, 13 Dec 2023 13:40:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-14 23:27:38.486384
- Title: PECANN: Parallel Efficient Clustering with Graph-Based Approximate
Nearest Neighbor Search
- Title（参考訳）: PECANN:グラフベースの近似近傍探索による並列クラスタリング
- Authors: Shangdi Yu, Joshua Engels, Yihao Huang, Julian Shun
- Abstract要約: 本稿では, 点集合の密度に基づくクラスタリングについて検討する。
密度ピークの異なる変種を単一のフレームワークPECANNに統合する。
PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
- 参考スコア（独自算出の注目度）: 8.15681999722805
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies density-based clustering of point sets. These methods use
dense regions of points to detect clusters of arbitrary shapes. In particular,
we study variants of density peaks clustering, a popular type of algorithm that
has been shown to work well in practice. Our goal is to cluster large
high-dimensional datasets, which are prevalent in practice. Prior solutions are
either sequential, and cannot scale to large data, or are specialized for
low-dimensional data.
This paper unifies the different variants of density peaks clustering into a
single framework, PECANN, by abstracting out several key steps common to this
class of algorithms. One such key step is to find nearest neighbors that
satisfy a predicate function, and one of the main contributions of this paper
is an efficient way to do this predicate search using graph-based approximate
nearest neighbor search (ANNS). To provide ample parallelism, we propose a
doubling search technique that enables points to find an approximate nearest
neighbor satisfying the predicate in a small number of rounds. Our technique
can be applied to many existing graph-based ANNS algorithms, which can all be
plugged into PECANN.
We implement five clustering algorithms with PECANN and evaluate them on
synthetic and real-world datasets with up to 1.28 million points and up to 1024
dimensions on a 30-core machine with two-way hyper-threading. Compared to the
state-of-the-art FASTDP algorithm for high-dimensional density peaks
clustering, which is sequential, our best algorithm is 45x-734x faster while
achieving competitive ARI scores. Compared to the state-of-the-art parallel
DPC-based algorithm, which is optimized for low dimensions, we show that PECANN
is two orders of magnitude faster. As far as we know, our work is the first to
evaluate DPC variants on large high-dimensional real-world image and text
embedding datasets.
- Abstract（参考訳）: 本稿では,ポイント集合の密度に基づくクラスタリングについて検討する。
これらの手法は、任意の形状のクラスターを検出するために、点の密度の高い領域を使用する。
特に,実際にうまく機能することを示す一般的なアルゴリズムである密度ピーククラスタリングの変種について検討した。
当社の目標は、一般的に普及している大規模な高次元データセットをクラスタ化することです。
従来のソリューションはシーケンシャルで、大きなデータにスケールできないか、低次元のデータに特化している。
本稿では,このアルゴリズムに共通するいくつかの重要なステップを抽象化することにより,密度ピークの異なる変種をひとつのフレームワークPECANNにまとめる。
そのような重要なステップの1つは述語関数を満たす近辺を探すことである。本論文の主な貢献の一つは、グラフに基づく近似近辺探索(anns)を用いて述語探索を行う効率的な方法である。
並列性を両立させるために,少数のラウンドで述語を満足する近傍近傍の点を見つけることができる二重探索手法を提案する。
提案手法は,PECANNに接続可能な既存のグラフベースANNSアルゴリズムにも適用可能である。
PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
高次元密度ピーククラスタリングのための最新のFASTDPアルゴリズムと比較すると,ARIの競合点を達成しつつ,最良のアルゴリズムは45x-734倍高速である。
低次元に最適化された最先端の並列DPCアルゴリズムと比較して,PECANNは2桁高速であることを示す。
私たちが知る限り、我々の研究は、大規模な高次元実世界画像とテキスト埋め込みデータセットでdpcの変種を評価する最初の方法です。
関連論文リスト
- A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-12-17T04:41:07Z) - PaVa: a novel Path-based Valley-seeking clustering algorithm [13.264374632165776]
本稿では,任意の形状のクラスタのための新しいパスベースのバレー探索クラスタリングアルゴリズムを提案する。
このアルゴリズムには3つの重要なテクニックが使われている。
その結果,パスに基づくバレー探索アルゴリズムは正確かつ効率的であることが示唆された。
論文 参考訳（メタデータ） (2023-06-13T02:29:34Z) - ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate
Nearest Neighbor Search Algorithms [5.478671305092084]
本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。
我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
論文 参考訳（メタデータ） (2023-05-07T19:28:23Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - 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) - ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering
using Nearest-Neighbor Chain [6.824747267214373]
本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。
従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。
我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
論文 参考訳（メタデータ） (2021-06-08T23:13: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) - Determinantal consensus clustering [77.34726150561087]
本稿では,クラスタリングアルゴリズムのランダム再起動における決定点プロセス (DPP) の利用を提案する。
DPPは部分集合内の中心点の多様性を好んでいる。
DPPとは対照的に、この手法は多様性の確保と、すべてのデータフェースについて良好なカバレッジを得るために失敗することを示す。
論文 参考訳（メタデータ） (2021-02-07T23:48:24Z) - LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set
Similarity Under Skew [58.21885402826496]
全ペアセットの類似性は、大規模で高次元のデータセットであっても広く使われているデータマイニングタスクである。
我々は,全対集合の類似性を近似するために,新しい分散アルゴリズム LSF-Join を提案する。
LSF-Joinは、小さな類似度閾値やスキュー入力セットであっても、最も近いペアを効率的に見つける。
論文 参考訳（メタデータ） (2020-03-06T00:06:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。