Informatics Seminar (Perspective in Informatics 4B) 2010 - 2011
December 10 (Fri), 16:30 - 18:00
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
Don't Rush into a Union: Take Time to Find Your Roots
- Speaker:
Mikkel Thorup (AT&T Labs Research)
- 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 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(log n / loglog n) and amortized
t_u = t_q = O(alpha(n)).
By contrast, we show that if t_u = o(log n / loglog 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(log 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(log n polyloglog n) upper bound.
Joint work with Mihai Patrascu.
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar