概要 - 低次元における並列階層的なクラスタリング

タイトル
低次元における並列階層的なクラスタリング

時間
2025-07-26 19:52:50

著者
{"MohammadHossein Bateni","Laxman Dhulipala","Willem Fletcher","Kishen N Gowda","D Ellis Hershkowitz","Rajesh Jayaram","Jakub Łącki"}

カテゴリ
{cs.DS,cs.CC,cs.DC}

リンク
http://arxiv.org/abs/2507.20047v1

PDF リンク
http://arxiv.org/pdf/2507.20047v1

概要

この論文では、低次元空間における階層的な凝集クラスタリング（HAC）に新たなアプローチを提案し、特に重心やWardのリンクなどの非単調なリンク関数に焦点を当てています。著者たちは、これらの関数が実務に不可欠であることを示し、一般的なアルゴリズムクラスを使用して効率的に並列化できることを証明しました。 **主要な貢献**: * **よく行動するリンク関数**: 研究では、ユークリッド距離に似た性質を持つよく行動するリンク関数の概念を導入し、重心とWardのリンクがよく行動することを示しました。 * **高さの界**: 著者たちは、よく行動するリンク関数を使用したHACで生成されるデンドログラムの高さが低次元では多項式（poly(log n)）であることを証明しました。この結果は、効率的な並列アルゴリズムの設計に重要です。 * **並列HAC**: 低高さのデンドログラムを持つHACのための並列アルゴリズムを提案し、これらのアルゴリズムは高さの界を利用し、最先端の並列最寄り要素検索データ構造を使用します。これらのアルゴリズムは、従来の並列アルゴリズムと比較してほぼ最適な作業効率を達成します。 * **高次元における難しさ**: 著者たちは、重心リンクを使用したHACが高次元でCC-hardであることを示し、効率的な並列アルゴリズムの存在が不可能であることを示唆しました。 **アルゴリズムの結果**: * **重心リンク**: k = O(1)のとき、(1 + ϵ)-近似の重心HACのためのO(1)深さとO(n)作業のアルゴリズムを提案しました。 * **Wardのリンク**: k = O(log log n / log log log n)のとき、(1 + ϵ)-近似のWardのHACのためのO(1)深さとO(n)作業のアルゴリズムを提案しました。 **影響**: * これらの結果は、非単調なリンク関数を使用したHACの複雑さについての新しい理解を提供します。 * 提案されたアルゴリズムは、低次元空間における効率的な並列クラスタリングのための実用的な解決策を提供します。 * 難しさの結果は、高次元におけるHACの並列化が困難であることを示唆します。 **全体として、この論文は階層クラスタリングの分野に重要な貢献をしています。低次元空間における並列HACに関する革新的な洞察と実用的なアルゴリズムを提供しています**。


推奨論文

ブロック符号化におけるアンシラ・オーバーヘッドを削減する方法

大規模言語モデルを用いた橋の状態評価のための非破壊評価プロファイル図の自動解釈

多スケールの神経PDEサローグラットの予測とダウンスケーリングへの適用：海流への応用

公開量子コンピュータ上での非侵襲的測定による時間の順序とLeggett-Garg不平等の検証

MC$^2$A: 高効率なマルコフ連鎖モンテカルロ加速のためのアルゴリズム・ハードウェア共設計を可能にする

第6世代（6G）無線ユニット用のFPGA SoCのための拡張可能なリソース管理レイヤー

MODA: マルチタスクターゲット意識型分子生成のための統一化3D拡散フレームワーク

DENSE: 病院訪問を横断する多様な臨床記録の時系列モデリングを用いた長期的な進捗ノート生成

RoCE BALBOA：スマートNIC向けのサービス強化型データセンターRDMA

MMBench-GUI: グラフィカルユーザインターフェースエージェントのための階層的多プラットフォーム評価フレームワーク