undefined | Better HN

0 pointseutectic5y ago0 comments

I think there's a paper somewhere claiming that completely random linking is just as good as union-by-rank (in expectation).

0 comments

moab5y ago

Yes, there's a few papers over the last few years on this, starting with this paper: https://www.cis.upenn.edu/~sanjeev/papers/soda14_disjoint_se...

Here is a more recent paper (from this year) analyzing concurrent union find with random linking: https://arxiv.org/pdf/2003.01203.pdf

bunsenmcdubbs5y ago

Woah these look great! Sad I didn't encounter them earlier.

Our team is actively working on improvements in this part of our data infrastructure (hence this project & blog post) so maybe there will be a follow up coming up with the next version of our Identity implementation...

KMag5y ago

Isn't that expected (within a constant factor of optimal depth, a.k.a. O(log N) tree height)? They're essentially building a treap, minus the in-order traversal of keys restriction.

[0] https://en.wikipedia.org/wiki/Treap

eutecticOP5y ago

Optimal depth for union-find is O(1); every node points directly to the root. It's a very different case than building a binary search tree.

j / k navigate · click thread line to collapse