@techreport{TD:100273,
	att_abstract={{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 $t_u$ be the time to
insert an edge and $t_q$ be the query time. For $t_u = Omega(t_q)$,
the problem is equivalent to the well-understood emph{union--find}
problem: $proc{InsertEdge}(s,t)$ can be implemented by
$proc{Union}(proc{Find}(s), proc{Find}(t))$. This gives worst-case
time $t_u = t_q = O(lg n / lglg n)$ and amortized $t_u = t_q =
O(alpha(n))$.

By contrast, we show that if $t_u = o(lg n / lglg n)$, the query
time explodes to $t_q ge n^{1-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 $t_u = o(t_q)$.

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 cdot (lglg
n)^{O(1)})$ upper bound.
}},
	att_authors={mp6431, mt2514},
	att_categories={},
	att_copyright={{ACM}},
	att_copyright_notice={{(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of ACM STOC'11. {{, 2011-06-06}}.
}},
	att_donotupload={},
	att_private={false},
	att_projects={},
	att_tags={},
	att_techdoc={true},
	att_techdoc_key={TD:100273},
	att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100273_DS1_2010-11-05T19:01:05.030Z.pdf},
	author={Mihai Patrascu and Mikkel Thorup},
	institution={{Proceedings of ACM STOC'11}},
	month={June},
	title={{Don't Rush into a Union: Take Time to Find Your Roots}},
	year=2011,
}