SemyonSinchenko commented on issue #198:
URL:
https://github.com/apache/datasketches-rust/issues/198#issuecomment-5264437429
@tisonkun
> May I ask where you'd like to use ThetaUnion?
I'm experimenting with a scalable graph algorithms (like a 10th of billion
edges graphs and beyond). There is a set of well known problems that requires
to estimate the neighbors overlap of two nodes. Something like node "X" has
neighbors {A, B, C}; node "Y" has neighbors {B, C, D}. | X intersect Y| = 1
In billion scale graphs there are so called "hubs", or nodes which degree
can be millions. Like an influencer in social network. An attempt to estimate
the overlap of two hubs would require to collect two huge sets of millions
size. That is problematic if you are trying to do so in parallel because it
creates load skew and can even kill a worker that is so unhappy that got two
hubs.
On the other hand, theta provides exactly what I need: fixed size structure.
The only problem was that during collecting neighbors in the map-reduce style,
when I processed one partition of the edges set and another I have theta
sketches that I need to union.
Something like this :)
Feel free to ask anything, I have code to show if you are interested and a
couple of scientific papers about using HLL / Theta for approximate graph
algorithms at scale.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
