In-database connected component analysis
Harald Bögeholz∗

Michael Brand†

Radu-Alexandru Todor‡

arXiv:1802.09478v1 [cs.DS] 26 Feb 2018

February 27, 2018

Abstract
We describe a Big Data-practical, SQL-implementable algorithm for efficiently determining connected components for graph data stored in a Massively Parallel Processing (MPP) relational database. The algorithm
described is a linear-space, randomised algorithm, always terminating with the correct answer but subject to
a stochastic running time, such that for any ǫ > 0 and any input graph G = hV, Ei the algorithm terminates
after O(log |V |) SQL queries with probability of at least 1 − ǫ, which we show empirically to translate to a
quasi-linear runtime in practice.

∗ Monash

University, Melbourne, Australia. Email: harald.boegeholz@monash.edu
University and Telstra Corporation, Melbourne, Australia. Email: michael.brand@monash.edu
‡ UBS, Zürich, Switzerland. Email: radu-alexandru.todor@ubs.com

† Monash

1

Introduction

Connected component analysis [14], the assignment of a label to each vertex in a graph such that two vertices
receive the same label if and only if they belong to the same connected component, is one of the tent-pole
algorithms of graph analysis. Its wide use is in applications ranging from image processing (e.g., [17, 29, 23, 32],
to name a few recent examples) to cyber-security (e.g., [9, 24, 13, 33]). The most well-known theoretical result
regarding connectivity analysis is perhaps the Union/Find algorithm [15, 30, 4], ensuring that labels can be
maintained per vertex in an amortised complexity on the order of the inverse Ackermann function per edge,
which is the theoretical optimum. In real-world settings, however, large graphs such as those analysed in Big
Data data science are stored in ways that make them ill-suited for the Union/Find algorithm. For example,
Union/Find involves following long linked lists which may refer to disparate locations on a disk drive, or, more
generally, may reside on separate disks altogether.
On the other hand, the potential to be stored on large servers or on multiple machines also entails certain
advantages. For example, in such an environment one should be able to process data in parallel. Indeed, many
researchers have long tried to optimise connected component finding for parallel computing environments (e.g.,
[12]). Most suited for this pursuit from a theoretical perspective is the theoretical framework of the Parallel
Random Access Machine (PRAM) [7, 26]. PRAM algorithms for connected components finding were presented,
e.g., in [28, 31, 1]. In [8], it was noted that randomised algorithms may have an advantage in this problem.
The best result obtained by the randomised approach is [10], where a randomised EREW PRAM algorithm is
presented that finds connected components of a graph G = hV, Ei in O(log |V |) time using an optimal number
of O((|V | + |E|)/ log |V |) processors. Its result is always correct and the probability that it does not complete
in O(log |V |) time is at most n−c for any c > 0.
However, as observed by Eppstein and Galil [6], the PRAM model is “commonly used by theoretical computer
scientists but less often by builders of actual parallel machines”. Its assumptions, which are idealisations of
the parallelised computation set-up, do not accurately reflect the realities of parallel computing architectures,
making its algorithms unrealistic to implement or not truly attaining the reported performance complexity
bounds.
Indeed, the papers that explore connected components algorithms for large-scale practical architectures (e.g.,
[2, 25, 18, 19]) do so using decidedly different algorithms. Also, some popular architectures [11] were developed
expressly with the intent of creating specialised solutions to support graph processing.
Nevertheless, most of the world’s transactional business data is stored natively in large, relational, SQLaccessible databases, and is only treated as graph data in certain contexts. It is therefore beneficial to have
an efficient solution for graph algorithms, and particularly for the connected components algorithm, within the
framework of relational databases, and specifically within the framework of Massively Parallel Processing (MPP)
databases [5] where the architecture is designed for efficient parallel processing. Such a solution obviates the
need for data duplication in a separate storage system and for supporting multiple data storage architectures
(usually from different vendors). It also avoids the potential for data conflicts, as well as the problems of having
to perform data analysis in two disparate systems that may not be able to communicate intermediate results
optimally (thus hampering analysis that requires tools from both worlds). As we demonstrate here, by running
all processing natively in an MPP database, the algorithm will smoothly scale out to Big Data, whereas most
other solutions (e.g., NoSQL databases) presently do not scale as well.
The present paper presents a new algorithm for connected components analysis, Randomised Contraction.
It uses SQL queries as its basic building blocks and is designed to minimise the number of such queries needed.
It uses (for any input graph) an expected logarithmic number of queries, running over exponentially decreasing
amounts of data, which our empirical results show to run, in total, in quasi-linear time, making the algorithm
practical in the context of in-database Big Data analytics.
A further criterion for the practicality of an in-database algorithm is that it does not unduly expand the
amount of required storage by introducing considerable intermediate data. Typical database maintenance does
not use all available space for storage (because many standard database operations create temporary tables),
but does use some bounded fraction of available space. Thus, practical in-database algorithms for use on mass
data should not create intermediate data that is more than linear in the amount of data being processed. Our
algorithm satisfies this criterion, too.
Like the PRAM algorithms of [8, 10], our algorithm is randomised. It is guaranteed to terminate and to
do so with a correct answer, and for any ǫ > 0 guarantees to terminate in O(log |V |) with probability at least
1 − ǫ, where |V | is the number of vertices in the input graph. The algorithm’s space requirements are linear
deterministically, not merely in expectation, and it can be implemented to use temporary storage not exceeding
1

four times the size of the input plus O(|V |), this being essentially a five-fold blow-up, which is within the typical
range for standard database operations.
Our empirical results show that Randomised Contraction outperforms other leading connected components
algorithms when implemented in an MPP database. Furthermore, the in-database implementations use fewer
resources than the native implementations of those algorithms in other distributed computing environments,
allowing them to scale up to larger datasets and resulting in faster execution.
The paper is structured as follows: in Section 2, we describe the problem formally. In Section 3, we discuss
naive approaches to a solution and show where they fail. In Section 4, we describe our new algorithm, Randomised Contraction, with several refinements, and analyse its theoretical performance in Section 5. Section 6
gives empirical results. A short conclusions section follows.

2

Problem description

A graph G = hV, Ei is typically stored in a relational database in the form of two tables. One stores the set of
vertices V , represented by a column of unique vertex IDs and optionally more columns with additional vertex
information. Another table stores the edge set E in two columns containing vertex IDs and optionally more
columns with additional edge information. Graphs are taken to be undirected, so an (x, y) edge is considered
identical to a (y, x) edge. For simplicity we present our algorithm such that its only input is an edge table
containing two columns with vertex IDs from which the set of vertices is deduced. Isolated vertices can be
represented in this table as “loop edges”, (v, v), if necessary.
The output of the algorithm is a single table with two columns, vertex and representative, containing
one row per vertex. In each row vertex is a vertex ID and representative is a label uniquely identifying the
connected component the vertex belongs to. A correct output of the algorithm is one where any two vertices
share the same representative value if and only if they belong to the same connected component. Connected
component analysis does not make any specific requirement regarding the values used to represent components,
except that they be comparable.

3

Simple solution attempts

Perhaps the simplest approach to performing in-database connected components analysis is to begin by choosing
for each vertex a representative by picking the vertex with the minimum ID among the vertex itself and all
its neighbours, then to improve on that representative by taking the minimum ID among the representatives
of the vertex itself and all its neighbours, and to continue in this fashion until no vertex changes its choice
of representative. We refer to this naive approach as the “Breadth First Search” strategy: after n steps each
vertex’s representative is the vertex with the minimum ID among all vertices in the connected component that
are at most at distance n from the original vertex.
Though the algorithm ultimately terminates and delivers the correct result, its worst-case runtime makes it
unsuitable for Big Data. Consider, for example, the sequentially numbered path graph with IDs 1, 2, . . . , n.
For this graph, Breadth First Search will take n − 1 steps.
To remedy this, consider an algorithm that calculates G2 , i.e., the graph over the same vertex set as G,
whose set of edges includes, in addition to the original edges, (x, z) for every x and z for which there exists a y
such that both (x, y) and (y, z) are edges in G.
Calculating G2 can be done easily in SQL by means of a self-join. A tempting possibility is therefore to
repeat the self-join and calculate G4 , G8 , etc.. Such a procedure would allow us to reach neighbourhoods of
radius 2n in only n steps.
Unfortunately, this second approach does not yield a workable algorithm, either. The reason for this is that
in Gk each vertex is directly connected to its entire neighbourhood of radius k in G. For a single-component G,
the result is ultimately the complete graph with |V |2 edges. This is a quadratic blow-up in data size, which for
Big Data analytics is unfeasible.
Our aim, in presenting a new algorithm, is therefore to enjoy the best of both worlds: we would like to
be able to work in a number of operations logarithmic in the size of the graph, but to require only linear-size
storage.

2

4

The new algorithm

We present our new algorithm for calculating connected components, Randomised Contraction, by starting
with its basic idea and refining it in several steps.

4.1

The basic idea

Let G = hV, Ei be a graph. The algorithm contracts the graph to a set of representative vertices, preserving
connectivity, and repeats that process until only isolated vertices remain. These then represent the connected
components of the original graph.
Denote by NG [v] the closed neighbourhood of a vertex v, i.e., the set of all vertices connected to v by an edge
in E plus v itself. Let G0 = hV0 , E0 i be the original graph.
At step i, map every vertex v to a representative ri (v) ∈ NGi−1 [v]. The contracted graph Gi = hVi , Ei i is
then constructed as Vi = {ri (v) | v ∈ Vi−1 } and Ei = {(ri (v), ri (w)) | (v, w) ∈ Ei−1 }. Note that two vertices are
connected in Gi−1 if and only if their representatives are connected in Gi . In other words, for each connected
component of Gi−1 there is a corresponding connected component in Gi .
The aim is to choose the representative functions ri in such a way that the graph shrinks as much as possible
at each step. Repeat this contraction process until reaching a graph Gk that contains only isolated vertices.
At that stage each of these represents one of the connected components of the original graph. Applying all the
maps ri in sequence maps each vertex to an identifier unique to its connected component: the composition of
the representative functions rk ◦ rk−1 ◦ · · · ◦ r1 is the output of the algorithm.

4.2

Randomisation

Assume the vertices of the graph are ordered. The basic idea for the choice of representatives is to choose
ri (v) = min NGi−1 [v]. Unfortunately, this approach still suffers from the same worst case as the breadth first
search strategy described in Section 3: it will take n − 1 steps on a sequentially numbered path graph with n
vertices.
The solution for avoiding this worst case is to randomise the order of the vertices at each step of the algorithm.
We will show in Section 5 that the graph will then, in expectation, shrink to at most a constant fraction γ of
its vertices with γ < 1, leading to an expected logarithmic number of steps.
To attain these performance bounds, random reordering must occur prior to each contraction step. This
keeps the probabilities governing each contraction independent from each other, allowing the good properties
that we will prove for each individual step to also manifest as global properties. As a result, the algorithm
behaves well for any input, as opposed to other algorithms that rely on a worst case input being “unlikely”.
Consider, however, adversarial scenarios, where such a worst case can be exploited to the attacker’s advantage.
We remark that this randomisation, critical to our algorithm, would not have aided the simple solution
attempts described in Section 3. The complexity of Breadth First Search, for example, is bounded by the
diameter of the analysed graph, regardless of how vertices are labelled.
In a practical implementation, choosing a random permutation of the vertices is itself a nontrivial task,
especially in a distributed computing scenario such as an MPP database. One way to achieve this is the
random reals method. At step i, generate for each vertex v a random real hi (v) uniformly distributed in
[0, 1]. The choice of the representative then becomes ri (v) = arg minw∈NG [v] hi (w).
i−1
This method in theory achieves full randomisation, a uniform choice among all |V |! possible orderings of the
vertices, for which the best performance bounds can be proved (see Appendix A). A practical implementation,
however, uses pseudo-random numbers, creating the problem that the total number of random bits required by
the method far exceeds the entropy content of any practical pseudo-random number generator. Furthermore, it
generates its random “reals” with only limited precision, creating a nonzero probability that the values assigned
to distinct vertices are not unique.
The advantage of the random reals method over brute-force random permutation generation is that the
table of random numbers can be created in parallel in a distributed database. While this process takes time
and requires additional space, its main disadvantage is that in order to pick representatives this table has to be
distributed to all machines in the cluster, creating an additional communication cost.
A more efficient idea is to pick a pseudo-random permutation by means of an encryption function on the
domain of the vertex IDs. This obviates the need to generate the random data and to communicate it across
the network, as each processor can compute it independently. If the vertex IDs are 64-bit integers, a suitable
3

choice is the Blowfish algorithm [27] which can be implemented in a database as a user-defined function. Let
ek denote an encryption function on the domain of the vertex IDs with key k. The encryption method then
works as follows: at step i, choose a random key ki . Let ri (v) = minw∈NGi−1 [v] eki (w).
Note that because of the use of min instead of arg min, ri (v) is no longer a vertex ID from the original graph
but a randomly generated integer. This does not affect the correctness of the algorithm, because the ultimate
connected component labels are not required to be vertex IDs, but merely to satisfy uniqueness. Uniqueness is
guaranteed by the fact that an encryption function is always a bijection. If it is for some reason preferable to
stick to the original vertex IDs, min can be be replaced by arg min above, leading to a slightly more complicated
implementation in SQL.
While encryption functions are designed to be “as random as possible” and work well in practice, it is
hard to rigorously prove for them the required graph contraction properties. Also, they are computationally
expensive. We therefore present as the final refinement of the Randomised Contraction algorithm the finite
fields method. Assume the domain of the vertex IDs is a finite field F with any ordering. To determine the
representatives at step i, choose 0 6= Ai ∈ F and Bi ∈ F uniformly at random and let ri (v) = minw∈NGi−1 [v] hi (w)
where hi (w) = Ai w + Bi . Again, min can be replaced by arg min if desired to choose the representatives among
the original vertex IDs. Because hi is calculated in a field, it is a bijection, guaranteeing the uniqueness of the
representative choices.
In practice, if the vertex IDs are fixed-size integers with b bits this data type can be treated as a finite field
with 2b elements. Since finite field arithmetic over this field is awkward to implement in SQL, we wrote a fast
implementation in C and loaded it as a user-defined function into the database. An SQL-only implementation
could alternatively choose a prime number p known to be larger than any vertex ID and use F = GF(p), which
amounts to using normal integer arithmetic modulo p. Note that while the calculation of hi (w) is performed
in the finite field F, the result is stored as an integer, and the calculation of the minimum (or arg min) is done
with reference to integer ordering.
Pseudocode of the algorithm as described is shown as Algorithm 1. Here, the list of edges, E, is given as the
input, and the vertices are inferred from E. Isolated vertices may be represented in the input as “loop edges”,
(v, v), if desired. Note that the algorithm begins with the duplication of all edges, as internally each edge of the
graph is treated as a pair of directed edges.
Algorithm 1 Randomised Contraction using finite fields (deterministic space usage)
procedure RandomisedContraction(E)
E ← E ∪ {(w, v) | (v, w) ∈ E}
⊲ setup
r(v) ← v for all v ∈ V
⊲ implicitly, V = {v | (v, w) ∈ E}
while E 6= ∅ do
choose random 0 6= A ∈ F and B ∈F and let h(v) = Av + B
r′ (v) ← min h(v), min(v,w)∈E h(w) for all v
r ← r′ ◦ r
⊲ see Section 4.3
E ← {(r′ (v), r′ (w)) | (v, w) ∈ E and r′ (v) 6= r′ (w)}
end while
return r
end procedure

4.3

Database implementation

An implementation of the Randomised Contraction algorithm in a relational database represents lists of edges
as tables with two columns for the vertex IDs. The data type of these columns is denoted by F, expressing
the fact that we need addition and multiplication operations on the domain of the vertex IDs that give it the
structure of a finite field. 64-bit integers are a natural choice.
In a distributed database, when creating an edge table it is important to use a distributed by annotation
to distribute this table by the first column. This causes all rows with the same value in the first column to
be stored on the same machine, allowing the aggregate function min over the second column to be calculated
locally for each first-column value and in parallel on all machines.
Functions like r, written in mathematical notation in the pseudocode, are represented as two-column tables
in the database with one column containing a vertex ID v and the other one containing the representative r(v).

4

Applying a representative function r′ to a vertex ID v, as required for the contraction step, is implemented by
joining the edge table to the representative table and looking up the value r′ (v) for each vertex v.
Function composition r′ ◦ r is implemented by creating a table that maps each vertex v in the domain of r
to the value r′ (r(v)). This is performed in SQL as a left outer join of the tables r and r′ . We set the result to
h(r(v)) where r′ (r(v)) is undefined.
Note that the edge table E gets smaller at each step: duplicate edges are removed and isolated vertices are
effectively excluded from further computation by dropping loop edges (v, v). The table representing r, however,
stays at the same size, having an entry for each vertex of the input graph. Algorithm 2 shows a faster way of
implementing the same idea using some more intermediate storage.
Algorithm 2 Randomised Contraction using finite fields (faster, stochastic space usage)
procedure RandomisedContractionF(E)
⊲ assuming E 6= ∅
E ← E ∪ {(w, v) | (v, w) ∈ E}
⊲ setup
i←0
while E 6= ∅ do
i← i+1
choose random 0 6= A ∈ F and B ∈ F and
 let hi (v) = Av + B
ri (v) ← min hi (v), min(v,w)∈Ei−1 hi (w) for all v
E ← {(ri (v), ri (w)) | (v, w) ∈ E and ri (v) 6= ri (w)}
end while
r ← ri
discard ri
while i > 1 do
i← i−1
r ← r ◦ ri
⊲ note implementation details
discard ri
end while
return r
end procedure
Here the intermediate tables ri get smaller at each step, but need to be stored throughout the execution of
the algorithm. The final result is then computed by joining the intermediate tables in reverse order. Here r ◦ ri
means a left outer join of the tables ri and r, where we set the result to hk (hk−1 (· · · hi+1 (v) · · · )) where ri (v)
is undefined.
Both algorithms compute the same result r = rk ◦rk−1 ◦· · ·◦r1 . Algorithm 1 calculates (rk ◦(rk−1 ◦· · ·◦(r2 ◦r1 )))
whereas Algorithm 2 calculates (((rk ◦ rk−1 ) ◦ · · · ◦ r2 ) ◦ r1 ).

5
5.1

Performance analysis
Time complexity

The critical observation regarding the Randomised Contraction algorithm is that at each iteration the number
of vertices drops at least by a constant factor γ < 1, in expectation. Here we will prove γ ≤ 3/4 for the
random reals method and the finite fields method. A better bound of 2/3 is proved in Appendix A in case of
full randomisation, such as with the random reals method. Note that we only need to consider graphs without
isolated vertices since all isolated vertices get removed at every step of the algorithm.
Proof. Let h(v) denote either the random number allotted to v by the random reals method or the pseudorandom number Av + B assigned by the finite fields method. Dividing the range of this function into an upper
and a lower half divides the vertices into “high” and “low” vertices.
For a vertex v to choose a high vertex as its representative, it must (1) itself be a high vertex, and (2) have
only high vertices as neighbours. Given that v is not isolated, let us pick an arbitrary neighbour of it, w, and
consider a weaker condition than (2): w must be a high vertex. The first condition occurs with probability
1/2 and the revised second condition occurs with independent probability 1/2 for the random reals method and
with probability less than 1/2 for the finite field method.

5

Table 1: Connected component algorithms
Algorithm
Randomised Contraction
Hash-to-Min [25]
Two-Phase [18]
Cracker [19]

Number of steps

Space

exp. O(log |V |)
O(log |V |)
O(log2 |V |)
O(log |V |)

exp. O(|E|)
O(|V |2 )
O(|E|)
|·|E|
O( |V
log |V | )

Thus, in expectation, no more than 1/4 of the vertices choose a high vertex as a representative, proving
that in total no more than 1/4|V | high vertices will be chosen as representatives. Even if all low vertices are
representatives, this still amounts to an expected number of no more than 3/4|V | representatives in total.
Given that the expected number of vertices that remain in any non-trivial connected component shrinks at
least by a factor of γ < 1 in every iteration, for some constant γ, the expected number of such vertices is bounded
by γ k |V | after k steps. This, in turn, bounds from above the probability of the algorithm not terminating after
k steps. We see, therefore, that for any fixed ǫ > 0, the algorithm reaches a termination probability of at least
1 − ǫ after logγ |V | + O(1) iterations, which is O(log |V |).

5.2

Space requirements

The Randomised Contraction algorithm can be implemented in two variants described above as Algorithm 1
and 2, both using the finite fields method. Both require Θ(|E|) space for storing the edge table E. Note that
the size of this edge table decreases at each step of the algorithm.
Algorithm 1 uses one table r of size Θ(|V |) and another table r′ starting at the same size and strictly
shrinking throughout the algorithm, so that space usage for these tables is bounded deterministically by Θ(|V |).
Algorithm 2 stores intermediate tables of size |V |, γ|V |, γ 2 |V |, . . . , γ k |V | in expectation which sums up to a
space usage of Θ(|V |) in expectation.
If the random reals method is used instead, both algorithms require an additional Θ(|V |) for storing a
random number for each vertex, which does not change the overall space complexity.
In summary, since |V | ≤ |E|, the space complexity of Algorithm 1 is Θ(|E|) deterministically while it is
Θ(|E|) + expected Θ(|V |) for Algorithm 2.
In practice, if the algorithms are implemented as shown, the edge table is blown up two-fold in the setup
stage. Also, at every iteration, a new edge table has to be generated before the old one is deleted, so up to 4|E|
space is required for storing the edge tables.

6

Empirical evaluation

To evaluate the practical performance of our Randomised Contraction algorithm we used the open source MPP
database Apache HAWQ (incubating) which runs on an Apache Hadoop cluster. Since SQL does not natively
support any control structures, we implemented Algorithm 2 as a Python script that connects to the database
and does all the “heavy lifting” using SQL queries. Finite field arithmetic over 64-bit integers was implemented
as a user-defined SQL function in C.
We compare Randomised Contraction to three other leading algorithms for calculating connected components
in a distributed computation setting. Their proven time and space complexities are summarised in Table 1.
Hash-to-Min and Two-Phase were implemented by their authors in MapReduce [20] whereas Cracker uses
Spark [16].
MapReduce algorithms can be translated to SQL by writing the key-value messages of the map stage to
temporary tables, telling the database to distribute them by key, and using aggregate functions for the reduce
phase. We implemented the two MapReduce algorithms in SQL in this way and similarly translated the Cracker
algorithm.
For Cracker, we were able to compare the performance of our database algorithm directly with the original
implementation published in [19]. The results of this comparison are that the translation to database language
not only substantially increased the speed of the algorithm but also reduced its memory requirements, allowing

6

Table 2: Datasets
Dataset
Andromeda
Candels10
Candels20
Candels40
Candels80
Candels160
RMAT26
RMAT28
Path100k
PathUnion10

|V |

|E|

1,459 M
83 M
166 M
332 M
663 M
1,326 M
39 M
49 M
100 k
154 M

2,287 M
238 M
483 M
975 M
1,958 M
3,923 M
2,079 M
8,590 M
100 k
154 M

components
62,166
39
48
91
224
617
5
1

k
k
k
k
k
k
k
k
1
10

it to scale up to much larger input graphs. In fact, the original implementation of [19] did not succeed executing
on even the smallest input graph in our test bench.
The authors of [25] and [18] did not publish original code, nor can we compare results-to-results because
they did not document their cluster configuration. [18] provides only relative timing results, but qualitative
descriptions given suggest that for these algorithms, too, the database implementation improved scalability and
at the very least did not reduce speed.
We compare the in-database performance of all four algorithms, showing that Randomised Contraction
consistently scales as expected. With the exception of a single (synthetic) input graph, Randomised Contraction
outperformed the other algorithms, and often by large factors.
For completeness, we also implemented our algorithm in Spark SQL. Results show that this version also
scales to larger graphs but is slower than the native database implementation.

6.1

Datasets

The datasets used are summarised in Table 2. To obtain real world examples of non-trivial size with interesting
properties we used the connected components algorithm as a simple image segmentation technique. We converted
a Gigapixel image (69, 536 × 22, 230 px) of the Andromeda galaxy [21] to a graph by generating an edge for
every pair of horizontally or vertically adjacent pixels with a colour difference below a certain threshold. The
vertex IDs were chosen at random so that they would not reflect the physical neighbourhood of pixels within
the original image.
The same technique can be applied to three-dimensional images such as medical images from MRI scans,
or to video. We used a 4K-UHD video of a flight through the CANDELS Ultra Deep Survey Field [22] and
converted some frames of it to a graph using pixel 6-connectivity (x, y, and time), again randomising the vertex
IDs. By using an increasing number of frames we generated a series of datasets (Candels10 . . . Candels160)
with similar properties and of increasing size for evaluating scalability of the algorithms.
All datasets created from images or video share the property that they contain a wide variety of component
sizes with a roughly scale-free distribution; see Figure 1 for an example (the single outlier is the black background). By contrast, the degrees of the vertices are mostly the same because of the construction of the graph:
4 for images, 6 for video.
To provide example graphs with a more diverse degree distribution, we used the R-MAT method [3] with
parameters (0.57, 0.19, 0.19, 0.05), which are the parameters used in [18]. With this method, we generated two
graphs based on an adjacency matrix of size 226 and 228 respectively (RMAT26 and RMAT28). Again, vertex
IDs were randomised to decouple the graph structure from artefacts of the generation technique.
As shown in the theoretical analysis, Randomised Contraction maintains its logarithmic and quasi-linear
performance bounds on any input graph, making it immune to adversarial attacks. By contrast, all other
algorithms examined have known worst-case inputs that exploit their weaknesses. To evaluate the impact of
these weaknesses, we have also included in our test bench the worst-case graphs. Path100k is a path graph with
100,000 sequentially numbered vertices causing large space usage in Hash-to-Min and Cracker. PathUnion10 is
a union of path graphs of different lengths, which is the worst case for the Two-Phase algorithm.

7

number of components

108
106
104
102
100
21

26

211
216
221
component size

226

231

Figure 1: Component sizes of Andromeda dataset
Table 3: Runtimes in seconds
Dataset
Andromeda
Candels10
Candels20
Candels40
Candels80
Candels160
RMAT26
RMAT28
Path100k
PathUnion10

6.2

RC

HM

TP

CR

5308
474
893
1764
3564
9143
2256
13021
90
431

–
3433
6479
15078
33606
–
4784
20685
6779
6100

37566
1653
3371
7394
16651
32995
3327
10014
37
4905

18790
962
2004
4169
9863
25289
3403
17153
7718
1169

In-database benchmark results

For performance measurements we used a database cluster consisting of five virtual machines with 64 GB
of RAM and 12 CPU cores (Intel Xeon E3 @ 2.6 GHz) each, running HAWQ version 2.2.0.0 as part of the
Hortonworks Data Platform 2.6.1. The tests were run on an otherwise idle database.
We have run each of the algorithms three times on each of the target data sets and measured the mean
and the standard deviation of the computation time. Like any other parallel processing, in-database execution
entails its own inherent variabilities, for which reason we did not expect even the deterministic algorithms to
complete in precisely consistent run-times. We did, however, expect the randomised algorithm to have somewhat
higher variability in its completion time. Observing the relative standard deviation (i.e., the ratio between the
standard deviation and the mean), the average value for Randomised Contraction was 1.9% as compared to
1.4%, 1.2%, and 1.4% for Hash-to-Min, Two-Phase, and Cracker, respectively. We conclude that the variability
added by randomisation is not, comparatively, very high.
Table 3 and Figure 2 show the average runtimes in seconds. Hash-to-Min did not finish on the Andromeda
and Candels160 datasets with the available resources. On all real world datasets Randomised Contraction
performed best, leading by a factor of 2 to 8 compared to the other algorithms. On the random graph RMAT26
the advantage is not as pronounced and on RMAT28 it takes 30% longer than Two-Phase.
The Two-Phase algorithm performs particularly well on RMAT28 because the R-MAT method generates
graphs with atypically small diameters. This allows the Two-Phase algorithm to finish in only 8 steps for
RMAT28. Randomised Contraction, on the other hand, took 20 or 21 steps, the typical number for graphs
having this number of vertices.
The sequence of Candels datasets, roughly doubling in size from one to the next, demonstrates the scalability

8

Table 4: Maximum space used in GB
Dataset

input

RC

HM

TP

CR

Andromeda
Candels10
Candels20
Candels40
Candels80
Candels160
RMAT26
RMAT28
Path100k
PathUnion10

60
6
13
25
51
102
54
224
0.003
4

276
27
55
110
221
443
217
896
0.013
20

–
21
42
86
172
–
120
416
173
16

115
12
24
48
96
193
86
302
0.005
8

263
24
50
100
201
403
169
556
111
20

Table 5: Total gigabytes written
Dataset

input

RC

HM

TP

CR

Andromeda
Candels10
Candels20
Candels40
Candels80
Candels160
RMAT26
RMAT28
Path100k
PathUnion10

60
6
13
25
51
102
54
224
0.003
4

552
48
97
196
394
790
257
947
0.032
48

–
148
295
618
1248
–
247
717
521
279

1768
93
179
369
774
1481
168
466
0.049
264

904
61
125
251
504
1009
176
564
471
116

of the Randomised Contraction algorithm. Its runtime is essentially linear in the size of the graph.
The large space usage of Hash-to-Min and Cracker on their worst case path graph also leads to a large
runtime. PathUnion10 demonstrates the worst case of the Two-Phase algorithm leading to 10 times the runtime
compared to Randomised Contraction.
Real world space usage of the algorithms has two aspects. Table 4 shows the size of the input dataset and the
maximum amount of storage used by the algorithms at any given time, taking into account the amount of space
freed by deleting temporary tables. Here the Two-Phase algorithm uses the least space on all datasets, taking
2 times or less than the storage of the input data set. Our time-optimised implementation of the Randomised
Contraction algorithm stays within the expected bounds.
Another, arguably more important metric for database implementations is the total amount of data written
to the database while executing the algorithms, detailed in Table 5. Here Randomised Contraction is best in
the worst case and real world cases and performs worse only on the artificial RMAT graphs.
This number is significant if the whole algorithm is implemented as a transaction in a database. A transaction
combines a number of database operations into one atomic operation that either succeeds as a whole or gets
undone completely (rollback ). In order to achieve this behaviour, most databases delete temporary tables only
at the successful completion of the whole algorithm, and therefore the actual amount of storage needed is as
stated in Table 5.

6.3

Database performance vs. Spark

In [19], Lulli et al. implement Cracker, an optimised version called Salty-Cracker, Hash-to-Min, and several
other algorithms in the distributed computing framework Spark [16]. Their published source code is memory
intensive and works within our resources only on smaller graphs.
For their most highly optimised version of the Cracker algorithm the dataset with the highest runtime was
“Streets of Italy” (19 M vertices, 20 M edges). The reported time was 1338 seconds, which was the best among

9

40,000

RC
HM
TP
CR

10,000

(did not finish)

20,000
(did not finish)

seconds

30,000

0
Andromeda Candels10 Candels20 Candels40 Candels80 Candels160 RMAT26

RMAT28

Figure 2: In-database execution times for real world and synthetic datasets
all algorithms compared. We ran our Randomised Contraction algorithm on this same dataset in-database and
it finished in 143 seconds. Our database implementation of the Cracker algorithm took 261 seconds.
Note the considerable difference between resources used: The implementation of [19] ran on five nodes with
128 GB of RAM and 32 CPU cores each. Our database cluster had half the RAM and less than half the CPU
cores. Also the database was configured as it might be in a real-world production environment, never allocating
more than 20% of the resources to a single query.
This demonstrates that in-database analytics is not merely a curiosity but a viable and scalable way of
efficiently executing algorithms on Big Data. As opposed to a hand-crafted implementation of an algorithm
in low-level Spark, an implementation in an MPP database profits from mature query optimisation, and this
advantage is likely to only increase due to the continuous, ongoing improvements in database technology.
Formulating one’s algorithm in the form of SQL queries also has advantages beyond in-database implementation, as it allows utilising it in other SQL and SQL-like execution environments. As an example, we implemented
the Randomised Contraction algorithm in Spark SQL using Spark 2.1.1 and ran it on the Candels10 dataset,
exported from the database as a distributed set of text files. This allowed the algorithm to scale up properly,
but we note that it was still slower in Spark SQL than when executing in the database. The runtime on our
cluster was roughly 2.3 times as long for the Spark SQL implementation as for the in-database one, despite
both executing the same SQL code. We conjecture that the main reason for this is the higher level of maturity
of the query optimisation that databases such as HAWQ provide.
We note that even this factor of 2.3 does not take into account the amount of time required to export the
data from the database for analysis or to re-import the results back into the database, operations that would
likely be required in a real world implementation.

7

Conclusions

We describe a novel algorithm for calculating the connected components of a graph that can be implemented
in SQL and efficiently executed in a massively parallel relational database. Its robustness against worst case
inputs and its scalability make it practical for Big Data analytics. The performance measured is not only due to
our algorithm’s ability to use a minimum number of SQL queries and to minimise the amount of data handled
by each query, but also due to the work of the database’s native, generic query execution optimiser.
With relational databases poised to remain the standard for storing transactional business data and with
query execution engines improving year to year, the Randomised Contraction algorithm demonstrates that indatabase processing can be a viable and competitive alternative to the more widely used Big Data processing

10

technologies. It does not require data replication into dedicated analysis environments, saving not only the cost
associated with this but also eliminating the problem of ensuring data consistency.

A

Bounds on graph contraction

The Randomised Contraction algorithm requires a random ordering of the vertices at each step to guarantee
that the number of representatives for the non-isolated vertices is, in expectation, not more than a constant
fraction γ of the non-isolated vertices. In the body of the paper we have proved γ ≤ 3/4, requiring only the
weaker form of randomisation that is achieved by the finite fields method. In this appendix we take a closer
look at graph contraction under full randomisation and prove a better bound of γ ≤ 2/3.
We generalise graph contraction to directed graphs. In a directed graph, let N + (v) be the out-neighbourhood
of a vertex v, i.e., the set of vertices w that are connected to v by an arc v → w. Likewise, denote by N − (v)
the in-neighbourhood of v: vertices w with an arc w → v. Let N + [v] = N + (v) ∪ {v} and N − [v] = N − (v) ∪ {v}
be the closed out- and in-neighbourhoods, respectively. Let the order of the vertices be chosen uniformly at
random among the |V |! possible orderings. The representative of a vertex v is then chosen from the closed
out-neighbourhood: r(v) = min N + [v].
The algorithm for undirected graphs is a special case where each edge is bidirectional, in particular N (v) =
N + (v) = N − (v) for all vertices v. We note that we do not know of any natural interpretation for the result of
running the Randomised Contraction algorithm using this definition on a directed graph. Certainly, the output
is not a division into connected components.
Theorem A.1. For every directed graph G with n vertices v that have nonempty N + (v), the expected number
of representatives for these vertices is at most γn, where γ = 2/3. This is a tight bound.
Proof. We will prove that the probability for any vertex v to not become a representative at all is at least as
large as for the same vertex to become the representative of exactly one vertex (possibly itself).
To do this, we have to consider the n! possible orderings of the vertices. We define an injective mapping,
f , from the orderings that lead to the latter case to those leading to the former, noting that the probability is
proportional to the number of such orderings. To represent a certain ordering, let L(v), the “label” of v, be its
ordinal number and denote by rL the representative choices under this ordering.
Let v be a vertex which is the representative of exactly one vertex. Then there are two possibilities:
1. The vertex is its own representative,
2. The vertex is the representative of another vertex.
In the first case, for all w ∈ N + (v), L(w) > L(v). Let ũ = arg maxw∈N + (v) L(w), and let f map this
labelling, L, to the new labelling, L′ , obtained by exchanging the labels of v and ũ. In the new labelling, ũ
is the representative of v and v cannot have become the representative of any other vertex because its label is
larger than before.
In the second case, v is the representative of exactly one vertex u ∈ N − (v). Then L(v) < L(u) and for all
w ∈ N − (v) \ {u} we have L(rL (w)) < L(v). Let L′ be the labelling obtained by exchanging the labels of u
and v. Then v is no longer the representative of u and again it cannot have become the representative of any
other vertex. Furthermore, u is its own representative and is the largest-labelled in-neighbour of v with that
property.
In order to prove that f is injective, we show that it can be inverted. Let L′ = f (L) and let ũ = rL′ (v) =
arg minw∈N + (v) L′ (w). Let L′′ be the labelling obtained from L′ by exchanging the labels of v and ũ. Then
rL′′ (v) = v. By examining L′′ we can tell apart the two cases. If L belongs to case 1, L′′ = L, so L′′ is a
case 1 labelling. Otherwise, L belongs to case 2, so W = {w ∈ N − (v) | w = rL′ (w)} is nonempty. Under this
assumption, let u = arg maxw∈W L′ (w) and note that because, by assumption, rL (u) = v, for all w ∈ N + [u]\{v},
L(w) > L(v) and in particular L(u) > L(v). Furthermore, because u and v are the only vertices to change their
label values in f , for every w with L(w) < L(v) or L′ (w) < L′ (v), L′ (w) = L(w). In particular, we know this
to be true for u′ = rL (v) = arg minw∈N + (v) L(w) for which, by the assumption, L(u′ ) < L(v). Consequently,
arg minw∈N + (v) L(w) = arg minw∈N + (v) L′ (w), so u′ = ũ. Note that because L(ũ) < L(v) < L(u), these three
vertices are known to be distinct. We conclude that
L′′ (u) = L′ (u) = L(v) > L(u′ ) = L′ (u′ ) = L′ (ũ) = L′′ (v).
11

(1)

Figure 3: Graph with highest known contraction factor γ
The only vertices to change their labels between L and L′′ are u, v and ũ. In particular, because we
know from L(ũ) < L(v) = L(rL (u)) that ũ is not in N + (u), we can infer that for all w ∈ N + (u) \ {v},
L′′ (w) = L(w) > L(v) = L′′ (u). Together with (1), we conclude that rL′′ (u) = v. This implies that L′′ is not
a valid case 1 labelling, showing that L′ emerged from case 2, so exchanging the labels of v and u in L′ will
restore the original labelling L.
Let R0 be the expected number of vertices that are not representatives of any vertex, let R1 be the expected
number of vertices that are representatives of exactly one vertex, and let R2+ be the expected number of the
remaining vertices: R0 + R1 + R2+ = n.
Because f is injective, we know R1 ≤ R0 , so we get
2R1 + R2+ ≤ n.

(2)

By counting the number of vertices being represented by each vertex we have
R1 + 2R2+ ≤ n.

(3)

Summing the last two equations and dividing by 3 we get
R1 + R2+ ≤

2
n,
3

(4)

which is the desired conclusion because R1 + R2+ is exactly the expected number of representatives.
To prove that the bound is tight, consider that γ = 2/3 is attained when G is the directed 3-cycle.
Note that the proven bound is only tight for directed graphs. The worst-case (highest) value of γ for
undirected graphs is an open question. The graph with the highest γ value known is the one depicted in
Figure 3. It has γ = 81215/144144 ≈ 56.343%.

B

Implementation in Python/SQL

In this section we show an excerpt of the implementation of the Randomised Contraction algorithm we used
to run the experiments. It has been stripped of some of the benchmarking instrumentation and all of the
surrounding infrastructure code. In the excerpt shown, dataset contains the name of the input table which is
assumed to contain the edge list of the graph in two columns v1 and v2, each containing a 64-bit vertex ID.
r . log exec () executes the SQL query passed as the third parameter and returns the number of rows generated. r .log drop() drops the indicated table. r .execute() executes miscellaneous SQL queries. r .axplusb(A,x,B)
computes the expression Ax+ B using finite field arithmetic over 64-bit integers. The user-defined SQL function
axplusb(A,x,B) does the same in the database.
r . l o g e x e c ( ” s e t u p ” , 0 , ””” \
c r e a t e t a b l e c c g r a p h as
s e l e c t v1 , v2 from {0}
uni on a l l
s e l e c t v2 , v1 from {0}
d i s t r i b u t e d by ( v1 ) ;
””” . format ( d a t a s e t ) )
roundno = 0

12

stack A = [ ]
stack B = [ ]
while True :
roundno += 1
c c r e p s = ” c c r e p s {} ” . format ( roundno )
r A = 0
while r A == 0 :
r A = random . r a n d i n t ( −2∗∗63 ,2∗∗63 −1)
r B = random . r a n d i n t ( −2∗∗63 ,2∗∗63 −1)
stack A . append ( r A )
stack B . append ( r B )
r . l o g e x e c ( ” c c r e p s ” , roundno , ””” \
c r e a t e t a b l e { c c r e p s } as
s e l e c t v1 v ,
l e a s t ( a x p l u s b ({A} , v1 , {B} ) , min ( a x p l u s b ({A} , v2 , {B} ) ) ) r e p
from c c g r a p h
group by v1
d i s t r i b u t e d by ( v ) ;
””” . format ( c c r e p s=c c r e p s , A=r A , B=r B ) )
r . l o g e x e c ( ” c c g r a p h 2 ” , roundno , ””” \
c r e a t e t a b l e c c g r a p h 2 as
s e l e c t r1 . r e p as v1 , v2
from ccgraph , {} as r1
where c c g r a p h . v1 = r1 . v
d i s t r i b u t e d by ( v2 ) ;
””” . format ( c c r e p s ) )
r . log d rop ( ” ccgraph ” )
g r a p h s i z e = r . l o g e x e c ( ” c c g r a p h 3 ” , roundno , ””” \
c r e a t e t a b l e c c g r a p h 3 as
s e l e c t d i s t i n c t v1 , r2 . r e p as v2
from ccgraph2 , {} as r2
where c c g r a p h 2 . v2 = r2 . v
and v1 != r2 . r e p
d i s t r i b u t e d by ( v1 ) ;
””” . format ( c c r e p s ) )
r . log d rop ( ” ccgraph2” )
r . e x e c u t e ( ” a l t e r t a b l e c c g r a p h 3 rename t o c c g r a p h ” )
i f g r a p h s i z e == 0 :
break
accA = 1
accB = 0
while True :
roundno −= 1
( accA , accB ) = ( r . a x p l u s b ( accA , stack A . pop ( ) , 0 ) , r . a x p l u s b ( accA , stack B . pop ( ) , accB ) )
i f roundno == 0 :
break
c c r e p s r = ” c c r e p s {} ” . format ( roundno )
c c r e p s r 1 = ” c c r e p s {} ” . format ( roundno+1)
r . l o g e x e c ( ” r e s u l t ” , roundno , ””” \
c r e a t e t a b l e tmp as
s e l e c t r1 . v as v , c o a l e s c e ( r2 . rep , a x p l u s b ({A} , r1 . rep , {B} ) ) as r e p
from { r1 } as r1 l e f t o u t e r j o i n
{ r2 } as r2
on ( r1 . r e p=r2 . v )
d i s t r i b u t e d by ( v ) ;
””” . format (A=accA , B=accB , r 1=c c r e p s r , r 2=c c r e p s r 1 ) )

13

r . log drop ( ccrepsr )
r . log drop ( ccrepsr1 )
r . e x e c u t e ( ” a l t e r t a b l e tmp rename t o {} ” . format ( c c r e p s r ) )
r . e x e c u t e ( ” a l t e r t a b l e c c r e p s 1 rename t o c c r e s u l t ” )
r . log d rop ( ” ccgraph ” )

Acknowledgments
Portions of the work described in this paper were done while the second author was employed at Pivotal Software,
Inc., and are covered by U. S. Patents.

References
[1] Awerbuch, B., and Shiloach, Y. New connectivity and MSF algorithms for shuffle-exchange network
and PRAM. Computers, IEEE Transactions on 100, 10 (1987), 1258–1263.
[2] Bader, D. A., and JáJá, J. Parallel algorithms for image histogramming and connected components
with an experimental study. In ACM SIGPLAN Notices (1995), vol. 30, ACM, pp. 123–133.
[3] Chakrabarti, D., Zhan, Y., and Faloutsos, C. R-mat: A recursive model for graph mining. In
Proceedings of the 2004 SIAM International Conference on Data Mining (2004), SIAM, pp. 442–446.
[4] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, vol. 3.
MIT Press Cambridge, MA, 2001, ch. 21.
[5] DeWitt, D. J., and Gray, J. Parallel database systems: The future of high performance database
processing. Communications of the ACM 36 (1992).
[6] Eppstein, D., and Galil, Z. Parallel algorithmic techniques for combinatorial computation. Ann. Rev.
Comput. 3 (1988), 233–283.
[7] Fich, F. E. The complexity of computation on the Parallel Random Access Machine. In Handbook
of Theoretical Computer Science, Volume A: Algorithms and Complexity, J. van Leeuwen, Ed. Elsevier,
Amsterdam, 1990, pp. 757–804.
[8] Gazit, H. An optimal randomized parallel algorithm for finding connected components in a graph. SIAM
Journal on Computing 20, 6 (1991), 1046–1067.
[9] Giani, A., Bitar, E., Garcia, M., McQueen, M., Khargonekar, P., Poolla, K., et al. Smart
grid data integrity attacks. Smart Grid, IEEE Transactions on 4, 3 (2013), 1244–1253.
[10] Halperin, S., and Zwick, U. An optimal randomized logarithmic time connectivity algorithm for
the EREW PRAM. In Proceedings of the Sixth Annual ACM symposium on Parallel Algorithms and
Architectures (1994), ACM, pp. 1–10.
[11] Han, J., Haihong, E., Le, G., and Du, J. Survey on NoSQL database. In Pervasive Computing and
Applications (ICPCA), 2011 6th International Conference on (2011), IEEE, pp. 363–366.
[12] Hirschberg, D. S., Chandra, A. K., and Sarwate, D. V. Computing connected components on
parallel computers. Communications of the ACM 22, 8 (1979), 461–464.
[13] Hogan, E., Hui, P., Choudhury, S., Halappanavar, M., Oler, K., and Joslyn, C. Towards a
multiscale approach to cybersecurity modeling. In Technologies for Homeland Security (HST), 2013 IEEE
International Conference on (2013), IEEE, pp. 80–85.
[14] Hopcroft, J., and Tarjan, R. Algorithm 447: Efficient algorithms for graph manipulation. Communications of the ACM 16, 6 (1973), 372–378.

14

[15] Hopcroft, J. E., and Ullman, J. D. Set merging algorithms. SIAM Journal on Computing 2, 4 (1973),
294–303.
[16] Karau, H., and Warren, R. High Performance Spark: Best Practices for Scaling and Optimizing Apache
Spark. O’Reilly, 2017.
[17] Kikuchi, K., Masuda, Y., Yamashita, T., Sato, K., Katagiri, C., Hirao, T., Mizokami, Y., and
Yaguchi, H. A new quantitative evaluation method for age-related changes of individual pigmented spots
in facial skin. Skin Research and Technology (2016).
[18] Kiveris, R., Lattanzi, S., Mirrokni, V., Rastogi, V., and Vassilvitskii, S. Connected components
in MapReduce and beyond. In Proceedings of the ACM Symposium on Cloud Computing (2014), ACM,
pp. 1–13.
[19] Lulli, A., Carlini, E., Dazzi, P., Lucchese, C., and Ricci, L. Fast connected components computation in large graphs by vertex pruning. IEEE Transactions on Parallel and Distributed Systems 28, 3
(2017), 760–773.
[20] Miner, D., and Shook, A. MapReduce design patterns: building effective algorithms and analytics for
Hadoop and other systems. O’Reilly, 2012.
[21] NASA, ESA, Dalcanton, J., Williams, B. F., Johnson, L. C., the PHAT team, and Gendler,
R. Sharpest ever view of the andromeda galaxy. http://www.spacetelescope.org/images/heic1502a/,
Jan. 2015. Accessed: January 23, 2018.
[22] NASA, ESA, Summers, F., DePasquale, J., Bacon, G., and (STScI), Z. L. A flight through
the candels ultra deep survey field. http://hubblesite.org/video/984/science, Sept. 2017. Accessed:
January 23, 2018.
[23] Nowosielski, A., Frejlichowski, D., Forczmański, P., Gościewska, K., and Hofman, R. Automatic analysis of vehicle trajectory applied to visual surveillance. In Image Processing and Communications
Challenges 7. Springer, 2016, pp. 89–96.
[24] Patil, G. P., Acharya, R., and Phoha, S. Digital governance, hotspot detection, and homeland
security. Encyclopedia of Quantitative Risk Analysis and Assessment (2007).
[25] Rastogi, V., Machanavajjhala, A., Chitnis, L., and Das Sarma, A. Finding connected components in map-reduce in logarithmic rounds. In Data Engineering (ICDE), 2013 IEEE 29th International
Conference on (2013), IEEE, pp. 50–61.
[26] Savage, J. E. Models of Computation: Exploring the Power of Computing, 1st ed. Addison-Wesley,
Boston, MA, USA, 1997.
[27] Schneier, B. Description of a new variable-length key, 64-bit block cipher (blowfish). In International
Workshop on Fast Software Encryption (1993), Springer, pp. 191–204.
[28] Shiloach, Y., and Vishkin, U. An O(log n) parallel connectivity algorithm. Journal of Algorithms 3,
1 (1982), 57–67.
[29] Song, W., Wu, D., Xi, Y., Park, Y. W., and Cho, K. Motion-based skin region of interest detection
with a real-time connected component labeling algorithm. Multimedia Tools and Applications (2016), 1–16.
[30] Tarjan, R. Efficiency of a good but not linear set union algorithm. Journal of the ACM (JACM) 22, 2
(1975), 215–225.
[31] Vishkin, U. An optimal parallel connectivity algorithm. Discrete Applied Mathematics 9, 2 (1984),
197–207.
[32] Wu, X., Yuan, P., Peng, Q., Ngo, C.-W., and He, J.-Y. Detection of bird nests in overhead catenary
system images for high-speed rail. Pattern Recognition 51 (2016), 242–254.
[33] Yip, M., Shadbolt, N., and Webber, C. Structural analysis of online criminal social networks. In
Intelligence and Security Informatics (ISI), 2012 IEEE International Conference on (2012), IEEE, pp. 60–
65.

15

