| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
Sorry, something went wrong.
| val (currSum, cnt) = ee.select(sum(col(SRC).cast(DecimalType(20, 0))), count("*")).rdd | ||
| val (currSum, cnt) = minNbrs1.select(sum(col(MIN_NBR).cast(DecimalType(20, 0))), count("*")).rdd |
There was a problem hiding this comment.
This is the convergence critieria correction.
Ref: Lemma 8 in paper https://dl.acm.org/doi/pdf/10.1145/2670979.2670997
Sorry, something went wrong.
| var minNbrs1: DataFrame = minNbrs(ee) // src >= min_nbr | ||
| .persist(intermediateStorageLevel) | ||
|
|
||
| var prevSum: BigDecimal = minNbrs1.select(sum(col(MIN_NBR).cast(DecimalType(20, 0))), count("*")).rdd |
There was a problem hiding this comment.
Is there any concern with an overflow by capping this at 20?
Sorry, something went wrong.
There was a problem hiding this comment.
added verification.
Sorry, something went wrong.
| var prevSum: BigDecimal = null | ||
|
|
||
| // compute min neighbors (including self-min) | ||
| var minNbrs1: DataFrame = minNbrs(ee) // src >= min_nbr |
There was a problem hiding this comment.
This makes sense to do the first minimization vector connection reduction outside of the while loop. +1
Sorry, something went wrong.
|
|
||
| // test convergence | ||
| minNbrs1 = minNbrs(ee) // src >= min_nbr | ||
| .persist(intermediateStorageLevel) |
There was a problem hiding this comment.
Within the termination of the while loop, should we also explicitly call unpersist() in order to remove the cache references to these pseudo-mutable vars that represent an immutable cache state?
Sorry, something went wrong.
There was a problem hiding this comment.
I will revisit and fix the persist/unpersist operations
Sorry, something went wrong.
|
Let's get the original reporter to confirm with the customer on their data to validate that the convergence correctness is fixed. Let's also be sure to clean up the persistence (as that is something that they complained about) due to the memory cache holding on to those orphan states that were persisted during iterative convergence. |
Sorry, something went wrong.
There was a problem hiding this comment.
Do we have test to validate the algorithm is correct?
Sorry, something went wrong.
I will generate some random graph to test. |
Sorry, something went wrong.
|
This is great! |
Sorry, something went wrong.
| Back | FazBrowse Home | New Git URL |
Fix connected component algorithm implementation:
The algorithm is described in this paper: https://dl.acm.org/doi/pdf/10.1145/2670979.2670997
Summary of the algorithm: essentially, the algorithm is doing "large-star" and "small-star" transformations over the graph,
until convergence (i.e. the transformation doesn't change graph structure),
graph = input_graph # input graph each node must has a unique and comparable label number while (! converged) { graph = large_star(graph) graph = small_star(graph) }large star transformation:
For each node U, finding the neighbor nodes V that has larger label than node U, and finding the node M that has the minimal label in the set of {*node_U_neighbor_node_set, node_U}, for every node V, generate an edge from V to M, the generated edges compose of the "large star" transformation output graph.
small star transformation:
For each node U, finding the neighbor nodes V that has smaller label than node U, and finding the node M that has the minimal label in the set of node_U_neighbor_node_set, for every node V, generate an edge from V to M, and additionally, generate an edge of U to M, the generated edges compose of the "small star" transformation output graph.
Convergence critieria:
Convergence means large star and small star transformation generates identical output graph, and we can prove that, the output graph has the same component connectivity, and the topology of the graph is the overall graph is a union of disjoint stars, one for each connected component, and each star has a center node with the minimal label in its connected component.
To check if the graph reaches convergence, we can check the sum of all nodes' "minimal label value in set {*neighbor_nodes, self_node}", the sum keeps decreasing for each pass of large-star / small-star transformation, once it stops decreasing, it means the graph reaches convergence, and we can get each node's connectivity component ID by calculating its "minimal label value in set {*neighbor_nodes, self_node}".
So, current graphframe connected component algorithm code has one error in convergence checking, I correct it in this PR.