图 书 馆
快速欧氏最小生成树算法，分析，和应用程序Fast Euclidean Minimum Spanning Tree: Algorithm, Analysis, and Applications |
|
| 课程网址: | http://videolectures.net/kdd2010_march_fem/ |
| 主讲教师: | William March |
| 开课单位: | 乔治亚理工学院 |
| 开课时间: | 2010-10-01 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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. |
| 关 键 词: | 欧几里德最小生成树问题; EMST算法; 对偶树算法 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-05-21：王淑红(课程编辑志愿者) |
| 阅读次数: | 415 |