![](https://csdnimg.cn/release/download_crawler_static/15792237/bg3.jpg)
The rest of this paper is organized as follows. Section 2 gives a review of some
related work. Section 3 presents the proposed data- dependent EMST method. Sec-
tion 4 shows the experimental comparisons. In Sect. 5, we give the conclusion and
future work.
2 Related Work
Work related to the method presented in this paper falls into two main categories:
EMST algorithms and density-based outlier detection methods.
2.1 MST Algorithms
For a given connected and weighted graph G ¼ E, VðÞ, Bor°uvka’s algorithm begins
with each vertex of a graph being a tree, and for each consecutive iteration, it selec ts the
shortest edge from a tree to another tree and combines them. This process continues
until all the trees are combined into one tree [12]. Proposed independently by Jarn´ık
[13], Prim [2] and Dijkstra [14] in 1930, 1957 and 1959, respectively, the famous
Prim’s algorithm first arbitrarily selects a vertex as a tree, and then repeatedly adds the
shortest edge that connects a new vertex to the tree, until all the vertices are included.
Proposed in 1956, Kruskal’s algorithm starts with sorting all the edges by their weights
in a non-decreasing order, treats each vertex as a tree, and iteratively combines the trees
by adding edges in the sorted order excluding those leading to a cycle until all the trees
are combined into one tree [1]. The time complexity of these classic MST algorithms is
O ElogVðÞ.
To construct an MST in the Euclidean setting, standard Prim’s algorithm requires a
quadratic running time. To be more efficient, in 1978, Bentley and Friedman [15]
proposed to use a kd-tree in Prim’s algorithm to enhance the search for the next edge to
add to the tree, which can reach an O NlogNðÞrunning time for most data distributions.
In 1985, Preparata and Shamos [16] gave a lower bound for the EMST problem of
NlogNðÞ, which has been the tightest known lower bound. In 1993, Callahan and
Kosaraju’s proposed Well-Separated Pair Decomposition (WSPD) [17] which forms
the basis of most recent EMST algorithms. The WSPD partitions data points into a set
of pairs of tree nodes such that the nodes in any pair are farther apart than the diameter
of either n ode. It can be shown that the WSPD has O NðÞpairs of nodes, and that the
MST is a subset of the edges formed between the closest pair of points in each pair of
nodes. In 2000, Narasimhan and Zachariasen applied WSPD to compute neighbors of
components for Boruvka’s algorithm to find edges of the MST [18]. However, the
constant in the O NðÞsize of the WSPD grows exponentially with the data dimension
and is often very large in practice. In 2010, March et al. presented a new dual-tree
algorithm for efficiently computing the EMST [19], which is superficially similar to the
method in [18] except that the WSPD is replaced by the new dual-tree data structure
and referred to in the following as FEMST algorithm. They used adaptive algorithm
analysis to prove the tightest (and possibly optimal) runtime bound for the EMST
problem to-date. Experiments conducted demonstrated the scalability of their met hod
on astronomical data sets.
A Fast Two-Level Approximate Euclidean Minimum Spanning Tree Algorithm 275