@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, }