2010 FastEuclideanMinimumSpanningTre

• (March et al., 2010) ⇒ William B. March, Parikshit Ram, and Alexander G. Gray. (2010). “Fast Euclidean Minimum Spanning Tree: Algorithm, Analysis, and Applications.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835882

Subject Headings:

Notes

• Categories and Subject Descriptors: F.2.0 Analysis of Algorithms and Problem Complexity: General; I.5.3 Clustering: Algorithms
• General Terms: Algorithms, Theory

Cited By

• http://scholar.google.com/scholar?q=%22Fast+euclidean+minimum+spanning+tree%3A+algorithm%2C+analysis%2C+and+applications%22+2010
• http://portal.acm.org/citation.cfm?id=1835882&preflayout=flat#citedby

Quotes

Author Keywords

Adaptive Algorithm Analysis, Euclidean Minimum Spanning Trees

Abstract

The Euclidean Minimum Spanning Tree problem has applications in a wide range of fields, and many efficient algorithms have been developed to solve it. We present a new, fast, general EMST algorithm, motivated by the clustering and analysis of astronomical data. Large-scale astronomical surveys, including the Sloan Digital Sky Survey, and large simulations of the early universe, such as the Millennium Simulation, can contain millions of points and fill terabytes of storage. Traditional EMST methods scale quadratically, and more advanced methods lack rigorous runtime guarantees. We present a new dual-tree algorithm for efficiently computing the EMST, use adaptive algorithm analysis to prove the tightest (and possibly optimal) runtime bound for the EMST problem to-date, and demonstrate the scalability of our method on astronomical data sets.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 FastEuclideanMinimumSpanningTre	William B. March Parikshit Ram Alexander G. Gray			Fast Euclidean Minimum Spanning Tree: Algorithm, Analysis, and Applications		KDD-2010 Proceedings		10.1145/1835804.1835882		2010