Don't rush into a union: take time to find your roots

TY - GEN

T1 - Don't rush into a union

T2 - 43rd ACM Symposium on Theory of Computing

AU - Patrascu, Mihai

AU - Thorup, Mikkel

N1 - Conference code: 43

PY - 2011

Y1 - 2011

N2 - We present a new threshold phenomenon in data structure lower bounds where slightly reduced update times lead to exploding query times. Consider incremental connectivity, letting tu be the time to insert an edge and tq be the query time. For tu = Omega(tq), the problem is equivalent to the well-understood union-find problem: proc{InsertEdge}(s,t) can be implemented by Union(Find(s), Find(t)). This gives worst-case time tu = tq = O(lg n / lg lg n) and amortized tu = tq = O(α(n)). By contrast, we show that if tu = o(lg n / lg lg n), the query time explodes to tq ≥ n1-o(1). In other words, if the data structure doesn't have time to find the roots of each disjoint set (tree) during edge insertion, there is no effective way to organize the information! For amortized complexity, we demonstrate a new inverse-Ackermann type trade-off in the regime tu = o(tq). A similar lower bound is given for fully dynamic connectivity, where an update time of o(lg n) forces the query time to be n 1-o(1). This lower bound allows for amortization and Las Vegas randomization, and comes close to the known O(lg n · (lg lg n) O(1)) upper bound.

AB - We present a new threshold phenomenon in data structure lower bounds where slightly reduced update times lead to exploding query times. Consider incremental connectivity, letting tu be the time to insert an edge and tq be the query time. For tu = Omega(tq), the problem is equivalent to the well-understood union-find problem: proc{InsertEdge}(s,t) can be implemented by Union(Find(s), Find(t)). This gives worst-case time tu = tq = O(lg n / lg lg n) and amortized tu = tq = O(α(n)). By contrast, we show that if tu = o(lg n / lg lg n), the query time explodes to tq ≥ n1-o(1). In other words, if the data structure doesn't have time to find the roots of each disjoint set (tree) during edge insertion, there is no effective way to organize the information! For amortized complexity, we demonstrate a new inverse-Ackermann type trade-off in the regime tu = o(tq). A similar lower bound is given for fully dynamic connectivity, where an update time of o(lg n) forces the query time to be n 1-o(1). This lower bound allows for amortization and Las Vegas randomization, and comes close to the known O(lg n · (lg lg n) O(1)) upper bound.

U2 - 10.1145/1993636.1993711

DO - 10.1145/1993636.1993711

M3 - Article in proceedings

SN - 978-1-4503-0691-1

SP - 559

EP - 567

BT - Proceedings of the forty-third annual ACM symposium on Theory of computing

PB - Association for Computing Machinery

Y2 - 6 June 2011 through 8 June 2011

ER -