論文の概要: PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2312.03940v3
• Date: Tue, 03 Jun 2025 15:39:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 04:22:50.314439
• 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コアマシン上で評価する。
• 参考スコア（独自算出の注目度）: 7.466687780705626
• 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つは、述語関数を満たす隣人を見つけることであり、この論文の主な貢献の1つは、グラフベースの近接近接探索(ANNS)を用いて、この述語探索を行う効率的な方法である。 並列性を両立させるために,少数のラウンドで述語を満足する近傍近傍の点を2倍に探索する手法を提案する。 提案手法は,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)

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

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