15 ms·
I think there's a paper somewhere claiming that completely random linking is just as good as union-by-rank (in expectation).
by eutectic 6y ago
I think there's a paper somewhere claiming that completely random linking is just as good as union-by-rank (in expectation).
- moab 6y agoYes, 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_set_union.pdf 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 https://arxiv.org/pdf/2003.01203.pdf
- bunsenmcdubbs 6y agoWoah 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...
- KMag 6y agoIsn'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 https://en.wikipedia.org/wiki/Treap
- eutectic 6y agoOptimal 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.