A Fast Two-Level Approximate Euclidean
Minimum Spanning Tree Algorithm
for High-Dimensional Data
Xia Li Wang
1(&)
, Xiaochun Wang
2
, and Xiaqiong Li
2
1
School of Information Engineering, Changan University, Xi’an 710061, China
xlwang@chd.edu.cn
2
School of Software Engineering,
Xi’an Jiaotong University, Xi’an 710049, China
xiaocchunwang@mail.xjtu.edu.cn,
xiaqiongli@stu.xjtu.edu.cn
Abstract. Euclidean minimum spanning tree algorithms run typically with
quadratic computational complexity, which is not practical for large scale high
dimensional datasets. In this paper, we propose a new two-level approximate
Euclidean minimum spanning tree algorithm for high dimensional data. In the
first level, we perform outlier detection for a given data set to identify a small
amount of boundary points and run standard Prim’s algorithm on the reduced
dataset. In the second level, we conduct a k-nearest neighbors search to com-
plete an approximate Euclidean Minimum Spanning Tree construction process.
Experimental results on sample data sets demonstrate the efficiency of the
proposed method while keeping high approximate precision.
Keywords: Euclidean minimum spanning tree
Minimum spanning tree
Approximate minimum spanning tree
Nearest neighbor search
1 Introduction
Finding a minimum spanning tree (MST) for a given connected graph is a fundamental
problem with diverse application domains and many efficient MST algorithms have
been developed. In today’s MST tasks, usually, a set of N d-dimensional data points is
given and the problem is commonly solved in the Euclidean setting, giving rise to the
so-called Euclidean minimum spanning tree (EMST) problem. In this case, there are
V ¼ N vertices and E ¼ NN 1ðÞ=2 edges in the complete graph, and standard EMST
algorithms, such as Kruskal’s[1] and Prim’s[2], have a time complexity roughly equal
to O dN
2
. For large-scale high- dimensional datasets, standard EMST algorithms will
lose its time performance. Fortunately, in many practical applications, an exact EMST
can be generally replaced by an approximate one without degrading the quality of the
final application.
Being a compact data representation of a given data set, EMST has been exten-
sively used in image segmentation [3, 4], cluster analysis [5–7], classification [8], and
manifold learning [9]. In particular, we are interested in EMST construction for cases
© Springer International Publishing AG, part of Springer Nature 2018
P. Perner (Ed.): MLDM 2018, LNAI 10935, pp. 273–287, 2018.
https://doi.org/10.1007/978-3-319-96133-0_21
剩余14页未读，继续阅读
资源评论
