Time-space trade-offs for predecessor search

ABSTRACT

We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an explicit problem which breaks this communication complexity barrier. In addition, our bounds give the first separation between polynomial and near linear space. Such a separation is inherently impossible by communication complexity.Using our lower bound technique and new upper bound constructions, we obtain tight bounds for searching predecessors among a static set of integers. Given a set Y of n integers of l bits each, the goal is to efficiently find PREDECESSOR (x) = max (y ∈ Y | y ≤ x). For this purpose, we represent Y on a RAM with word length b using S ≥ nl bits of space. Defining a = lg S/n, we show that the optimal search time is, up to constant factors: min(log_bn, lgl-lg n / n, lg(l/a) / lg(a/lg n * lg l/a), lg (l/a) / lg (lg (l/a) / lg (lg n / a)).In external memory (b > l), it follows that the optimal strategy is to use either standard B-trees, or a RAM algorithm ignoring the larger block size. In the important case of b = l = γ lg n, for γ > 1 (i.e. polynomial universes), and near linear space (such as S = n • lg^O(1) n), the optimal search time is Θ(lg l). Thus, our lower bound implies the surprising conclusion that van Emde Boas' classic data structure from [FOCS'75] is optimal in this case. Note that for space n^1+ε, a running time of O(lg l / lg lg l) was given by Beame and Fich [STOC'99].

REFERENCES

• 1: M. Ajtai. A lower bound for finding predecessors in Yao's cell probe model. Combinatorica, 8(3):235--247, 1988.
• 2: N. Alon and J. Spencer. The Probabilistic Method. John Wiley, 2nd edition, 2000.
• 3: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002 [doi>10.1006/jcss.2002.1822]
• 4: Amit Chakrabarti , Oded Regev, An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.473-482, October 17-19, 2004 [doi>10.1109/FOCS.2004.12]
• 5: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 6: A. Feldmann and S. Muthukrishnan. Tradeoffs for packet classification. In Proc. IEEE INFOCOM, pages 1193--1202, 2000.
• 7: M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
• 8: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 9: A. Gál and P. B. Miltersen. The cell probe complexity of succinct data structures. In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP), pages 332--344, 2003.
• 10: Peter Bro Miltersen, The Bit Probe Complexity Measure Revisited, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.662-671, February 25-27, 1993
• 11: Peter Bro Miltersen, Lower bounds for union-split-find related problems on random access machines, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.625-634, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195415]
• 12: P. B. Miltersen. Cell probe complexity - a survey. In 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 1999. Advances in Data Structures Workshop.
• 13: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, v.57 n.1, p.37-49, Aug. 1998 [doi>10.1006/jcss.1998.1577]
• 14: P. Sen and S. Venkatesh. Lower bounds for predecessor searching in the cell probe model. arXiv:cs.CC/0309033. See also ICALP'01, CCC'03, 2003.
• 15: Mikkel Thorup, Space efficient dynamic stabbing with fast queries, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780636]
• 16: P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99--127, 1977. Announced by van Emde Boas alone at FOCS'75.
• 17: D. E. Willard. Log-logarithmic worst-case range queries are possible in space Θ (N). Information Processing Letters, 17(2):81--84, 1983.
• 18: Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

General Terms:
Algorithms, Performance, Theory

Keywords:
cell-probe complexity, lower bounds, predecessor search