Don't Rush into a Union: Take Time to Find Your Roots

Details Don't Rush into a Union: Take Time to Find Your Roots Don't Rush into a Union: Take Time to Find Your Roots

2011-02-09

arxiv.org/abs/1102.1783v2

Computer Science

Data Structures and Algorithms

To appear in STOC'11

Scientific paper

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 union-find problem: InsertEdge(s,t) can be implemented by Union(Find(s), 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 >= 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 * poly(lglg n)) upper bound.

Affiliated with

Also associated with

No associations

Rating

Don't Rush into a Union: Take Time to Find Your Roots does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Don't Rush into a Union: Take Time to Find Your Roots, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Don't Rush into a Union: Take Time to Find Your Roots will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-649919