Theorems relevant for Architecture

- CAP Theorem

Approximations relevant for Algorithms

- Stirling’s approximation
- Chebyshev’s inequality

Theorems relevant for Architecture

- CAP Theorem

Approximations relevant for Algorithms

- Stirling’s approximation
- Chebyshev’s inequality

In the previous post I have attempted to make a case that it is feasible to perform some graph processing, (specifically the problem of finding components in a graph given edges), in query languages using user-defined-aggregation-functions.

The approach relied on going over edges one by one and continuously build up components. The components were built as a <Key, Value> pair where Key was the node and the Value was the array of nodes constituting a component.

For example for a dataset like this

N1,N3

N1,N5

N2,N1

N2,N6

N7,N8

N10,N11

N20,N4

N9,N4

Below would be the result

{“N9”:[“N20″,”N4″,”N9″],”N5”:[“N1″,”N3″,”N5″,”N2″,”N6″],”N6”:[“N1″,”N3″,”N5″,”N2″,”N6″],”N7”:[“N7″,”N8″],”N8”:[“N7″,”N8″],”N1”:[“N1″,”N3″,”N5″,”N2″,”N6″],”N2”:[“N1″,”N3″,”N5″,”N2″,”N6″],”N3”:[“N1″,”N3″,”N5″,”N2″,”N6″],”N20”:[“N20″,”N4″,”N9″],”N4”:[“N20″,”N4″,”N9″],”N10”:[“N10″,”N11″],”N11”:[“N10″,”N11”]}

The above approach gives results in a map structure that is easier to join with other tables.

This approach as we noted in earlier post could need considerable compute power as the number of edges increase. This is due to the fact that as number of edges increase the component size inturn increases and this leads to O(n^3) complexity for the merge method which is considerable.

We also noted in the earlier post that a better approach would be to implement Weighted Quick Union with Path Compression(WQUPC) algorithm which has several optimizations ontop of the map approach. Some of them include

- Build trees to represent clusters.
- Reduce depth of individual trees as the algorithm progresses through edges.
- Use integer arrays vs heavier data structures
- No repetitions of clusters

NOTE: This approach would need atleast one array as big as the number of nodes in the graph.

There is one challenge in implementing the above approach in a horizontal-scale cluster setup ex: in Hadoop-Hive ecosystem.

Sets of edges need to be looked at in parallel and partial results need to be merged.

Below is an attempt at implementing WQUPC in Hive as an UDAF.

- Code – ConnectedComponentsWQUPC.java
- Results – Generate components and generate mappings from nodes to components

Below is the result in the form of <Node, Root of the cluster tree>

N9 N4

N8 N8

N7 N8

N6 N5

N5 N5

N4 N4

N3 N5

N20 N4

N2 N5

N11 N11

N10 N11

N1 N5

This approach is very close to O(m* log(n)) complexity where n is the number of edges and m is the number of connections.

It easily scales to 10s of millions of edges.