Disjoint set union with randomized linking

Ashish Goel; Sanjeev Khanna; Daniel H. Larkin; Robert E. Tarjan

doi:10.1137/1.9781611973402.75

Disjoint set union with randomized linking

Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Scopus citations

Abstract

A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naive linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.

Original language	English (US)
Title of host publication	Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Publisher	Association for Computing Machinery
Pages	1005-1017
Number of pages	13
ISBN (Print)	9781611973389
DOIs	https://doi.org/10.1137/1.9781611973402.75
State	Published - 2014
Event	25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States Duration: Jan 5 2014 → Jan 7 2014

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Country/Territory	United States
City	Portland, OR
Period	1/5/14 → 1/7/14

All Science Journal Classification (ASJC) codes

Software
Mathematics(all)

Access to Document

10.1137/1.9781611973402.75

Cite this

@inproceedings{6cc36b510a2b48b3a4d26c512bae6209,

title = "Disjoint set union with randomized linking",

abstract = "A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naive linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.",

author = "Ashish Goel and Sanjeev Khanna and Larkin, {Daniel H.} and Tarjan, {Robert E.}",

year = "2014",

doi = "10.1137/1.9781611973402.75",

language = "English (US)",

isbn = "9781611973389",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "1005--1017",

booktitle = "Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014",

}

Goel, A, Khanna, S, Larkin, DH & Tarjan, RE 2014, Disjoint set union with randomized linking. in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 1005-1017, 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, United States, 1/5/14. https://doi.org/10.1137/1.9781611973402.75

Disjoint set union with randomized linking. / Goel, Ashish; Khanna, Sanjeev; Larkin, Daniel H. et al.
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, 2014. p. 1005-1017 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Disjoint set union with randomized linking

AU - Goel, Ashish

AU - Khanna, Sanjeev

AU - Larkin, Daniel H.

AU - Tarjan, Robert E.

PY - 2014

Y1 - 2014

N2 - A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naive linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.

AB - A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naive linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.

UR - http://www.scopus.com/inward/record.url?scp=84902097285&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902097285&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.75

DO - 10.1137/1.9781611973402.75

M3 - Conference contribution

AN - SCOPUS:84902097285

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1005

EP - 1017

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -

Disjoint set union with randomized linking

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this