論文の概要: FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data
- arxiv url: http://arxiv.org/abs/2507.14261v1
- Date: Fri, 18 Jul 2025 12:53:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-22 20:51:31.810035
- Title: FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data
- Title（参考訳）: FAMST:大規模・高次元データのための高速近似最小スパンニングツリー構築
- Authors: Mahmood K. M. Almansoori, Miklos Telek,
- Abstract要約: Fast Approximate Minimum Spanning Tree (FAMST)は、最小スパンニングツリー(MST)を構築する際の計算課題に対処する新しいアルゴリズムである。
FAMSTは、数百万のポイントと数千の次元を持つデータセットに対するMSTベースの分析を可能にし、MST技術の適用性を、以前は不可能と考えられていた問題スケールにまで拡張する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We present Fast Approximate Minimum Spanning Tree (FAMST), a novel algorithm that addresses the computational challenges of constructing Minimum Spanning Trees (MSTs) for large-scale and high-dimensional datasets. FAMST utilizes a three-phase approach: Approximate Nearest Neighbor (ANN) graph construction, ANN inter-component connection, and iterative edge refinement. For a dataset of $n$ points in a $d$-dimensional space, FAMST achieves $\mathcal{O}(dn \log n)$ time complexity and $\mathcal{O}(dn + kn)$ space complexity when $k$ nearest neighbors are considered, which is a significant improvement over the $\mathcal{O}(n^2)$ time and space complexity of traditional methods. Experiments across diverse datasets demonstrate that FAMST achieves remarkably low approximation errors while providing speedups of up to 1000$\times$ compared to exact MST algorithms. We analyze how the key hyperparameters, $k$ (neighborhood size) and $\lambda$ (inter-component edges), affect performance, providing practical guidelines for hyperparameter selection. FAMST enables MST-based analysis on datasets with millions of points and thousands of dimensions, extending the applicability of MST techniques to problem scales previously considered infeasible.
- Abstract（参考訳）: 我々は,大規模かつ高次元のデータセットに対して,最小スパンニングツリー(MST)を構築する際の計算課題に対処する新しいアルゴリズムであるFAMSTを提案する。
FAMSTはANNグラフ構築、ANN相互接続、反復エッジ改善という3段階のアプローチを採用している。
$d$次元空間における$n$ポイントのデータセットに対して、FAMSTは$\mathcal{O}(dn \log n)$時間複雑性と$\mathcal{O}(dn + kn)$空間複雑性を達成する。
多様なデータセットにわたる実験により、FAMSTは正確なMSTアルゴリズムと比較して1,000$\times$のスピードアップを提供しながら、驚くほど低い近似誤差を達成することが示された。
我々は、キーのハイパーパラメータ、$k$(隣のサイズ)と$\lambda$(コンポーネント間エッジ)がパフォーマンスにどのように影響するかを分析し、ハイパーパラメータの選択の実践的なガイドラインを提供します。
FAMSTは、数百万のポイントと数千の次元を持つデータセットに対するMSTベースの分析を可能にし、MST技術の適用性を、以前は不可能と考えられていた問題スケールにまで拡張する。
関連論文リスト
- Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees [7.2092555743847155]
任意の距離空間における$n$ポイントの最小スパンニングツリー(MST)を見つけることは、階層的クラスタリングや他の多くのMLタスクの基本的なプリミティブである。
まず,(1)実践的手法を用いて不連結成分の森を発見し,(2)森林の不連結成分を分布木に接続するためのエッジの小さな重み集合を見出した。
2番目のステップを最適に解くには、まだ$Omega(n2)$時間が必要ですが、サブクワッドラティックな2.62近似アルゴリズムを提供しています。
論文 参考訳（メタデータ） (2025-02-18T16:13:46Z) - Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
教師なしの地上距離学習アプローチが導入されました
一つの有望な選択肢はワッサーシュタイン特異ベクトル(WSV)であり、特徴量とサンプルの間の最適な輸送距離を同時に計算する際に現れる。
木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。
論文 参考訳（メタデータ） (2024-11-11T23:21:01Z) - Faster Private Minimum Spanning Trees [11.72102598708538]
本稿では,時間内で動作中の既存手法の実用性に適合する新しい差分プライベートMSTアルゴリズムを提案する。
我々は,少なくとも$O(n2)$カットエッジを$O(sqrtn log n)$ timeでサンプリングすることのできるデータ構造を示す。
論文 参考訳（メタデータ） (2024-08-13T16:00:30Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Online Algorithm for Node Feature Forecasting in Temporal Graphs [12.667148739430798]
本稿では,時間グラフのノード特徴を予測するためのオンラインmspaceを提案する。
mspaceは最先端技術と同等に動作し、いくつかのデータセットでそれらを上回ります。
また,ノード特徴予測手法の評価を支援するために,合成データセットを生成する手法を提案する。
論文 参考訳（メタデータ） (2024-01-30T07:31:51Z) - Scalable network reconstruction in subquadratic time [0.0]
本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。
我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。
本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
論文 参考訳（メタデータ） (2024-01-02T19:00:13Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - GBMST: An Efficient Minimum Spanning Tree Clustering Based on
Granular-Ball Computing [78.92205914422925]
多粒度グラニュラバルと最小スパンニングツリー(MST)を組み合わせたクラスタリングアルゴリズムを提案する。
粒度が粗い粒状ボールを構築し,さらに粒状ボールとMSTを用いて「大規模優先度」に基づくクラスタリング手法を実装した。
いくつかのデータセットの実験結果は、アルゴリズムの威力を示している。
論文 参考訳（メタデータ） (2023-03-02T09:04:35Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Low Complexity Sequential Search with Size-Dependent Measurement Noise [19.201555109949677]
本稿では、エージェントが任意の時間にその領域にターゲットが存在するかどうかを問い合わせる領域を選択することができるターゲットローカライゼーション問題について考察する。
アレイ処理における初期ビームアライメント、ネットワークにおける重ヒッタ検出、ロボット工学におけるビジュアルサーチといった実用的応用により、我々は事実上重要な複雑さの制約/指標を考察する。
新規検索戦略として$dyaPM$と$hiePM$が提案されている。
論文 参考訳（メタデータ） (2020-05-15T22:40:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。