14
$\begingroup$

Are results known which rule out the existence of "too-good-to-be-true" data structures?

For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz and Sleator STOC '87) and still obtain $\mathcal{O}(1)$ time operations?

Or: can one implement an ordered set with integer keys and $\mathcal{O}(1)$ time operations? Of course this is at least as hard as discovering a linear time algorithm for sorting integers.

Has the answer been proven to be no for either of these questions? Are lower bound results known for any natural data structure?

$\endgroup$
  • $\begingroup$ Things change if we are able to add limitations to the problem space. For example, if we have a limited set of keys and enough memory, we may sort them in linear time using a bit vector. $\endgroup$ – jetru Mar 16 '11 at 11:55
  • 1
    $\begingroup$ I think the reason you're not getting too many answers to this question is that there are just so many possibilities. Many, many data structures have known lower bounds, and it's hard not to just stumble over them. A Google search for "data structure" "lower bound" includes, for me, 5 papers that have yet to be mentioned in this thread. I think you would have more success getting your question answered if you restricted it, perhaps by removing the part about "natural data structure[s]" and just asking about list maintenance or integer ordered sets (but not both in one question). $\endgroup$ – jbapple Mar 17 '11 at 7:15
  • $\begingroup$ I omitted that the 5 papers I found in the Google search were on just the first page of the search results. $\endgroup$ – jbapple Mar 17 '11 at 7:39
  • $\begingroup$ @jbapple: You are right! I think that the clicks from people in this community trying to help me with my question have pushed the good results to the top of the list. (For example, THIS page is now on the list!) I don't recall it being useful when I first did the search, or I likely would have restricted the question as you suggest. (Or I was a big dummy, that's possible too. :) ) $\endgroup$ – Shaun Harker Mar 17 '11 at 16:29
19
$\begingroup$

There is a really nice talk on the dynamic lower bounds on graphs by Mihai Pătraşcu. In summary (on p.20 of the slides), we have the lower bounds in terms of query time $t_q$ and update time $t_u$ (insert an edge):

enter image description here

See the paper for details. Some other papers by Mihai are relevant and nice, too.

UPDATE: I found that his PhD thesis "Lower Bound Techniques for Data Structures" providing lower bounds for many central data-structure problems using the techniques he developed. It certainly worths a read.

$\endgroup$
  • 1
    $\begingroup$ That thesis is wonderful, thank you very much for sharing the link. $\endgroup$ – Shaun Harker Mar 18 '11 at 5:20
6
$\begingroup$

The answer to any of your questions depends upon the model of computation. For instance, on many machines, multiplying integers is more expensive than adding them. Some models reflect this, while some do not.

For an answer to your question about ordered sets of integers, Andersson and Thorup discuss an asymptotically optimal solution to maintaining a dynamic ordered set of integers in the RAM model in polynomial space in their paper "Dynamic ordered sets with exponential search trees". The bound they achieve is $O(\sqrt{\log n/ \log \log n})$. The paper the cite for the lower bound is Beame and Fich's "Optimal Bounds for the Predecessor Problem and Related Problems".

$\endgroup$
  • $\begingroup$ Nice. But it seems you've overstated the result in the Andersson and Thorup paper. It applies only to linear space structures, not all polynomial space structures. $\endgroup$ – Shaun Harker Mar 17 '11 at 19:41
  • 2
    $\begingroup$ Andersson and Thorup cite Beame and Fich for the polynomial space: "The lower bound follows from a result of Beame and Fich. It shows that even if we just want to support insert and predecessor operations in polynomial space, one of these two operations have a worst-case bound of Ω(sqrt(log n/log log n)), matching our common upper bound. We note that one can find better bounds and trade-offs for some of the individual operations. Indeed, we will support min, max, predecessor, successor, and delete operations in constant time, and only do insert and search in Θ(sqrt(log n/log log n)) time." $\endgroup$ – jbapple Mar 18 '11 at 2:09
  • $\begingroup$ I see, the linear space comes in to advertise the upper bound, but Corollary 3.10 of Beame and Fich gives the poly-space lower bound, as you stated and I foolishly contradicted. It also occurs to me that one might want to advertise worst-case times for upper bounds while advertising amortized times for lower bounds. The Andersson and Thorup paper indeed cites (page 5) Beame and Fich for an amortized lower (and upper) bound. But Corollary 3.10 only seems to give the lower bound for worst-case. Perhaps someone could give me a hint on that as well? $\endgroup$ – Shaun Harker Mar 18 '11 at 4:25
2
$\begingroup$

In extension to what you mention to your question, one classic example is using the fact that integers cannot be sorted using comparisons faster than $O(n \log n)$ in order to prove the non-existence of superstructures.

Furthermore, it is not unusual to use information theory arguments (e.g. Kolmogorov complexity) in order to prove lower bounds for data structures.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.