Randomization does not help searching predecessors

ABSTRACT

At STOC'06, we presented a new technique for proving cell-probe lower bounds for static data structures with deterministic queries. This was the first technique which could prove a bound higher than communication complexity, and it gave the first separation between data structures with linear and polynomial space. The new technique was, however, heavily tuned for the deterministic worst-case, demonstrating long query times only for an exponentially small fraction of the input. In this paper, we extend the technique to give lower bounds for randomized query algorithms with constant error probability.

Our main application is the problem of searching predecessors in a static set of n integers, each contained in a l-bit word. Our trade-off lower bounds are tight for any combination of parameters. For small space, i.e. n^1+o(1), proving such lower bounds was inherently impossible through known techniques. An interesting new consequence is that for near linear space, the classic van Emde Boas search time of O(lg l) cannot be improved, even if we allow randomization. This is a separation from polynomial space, since Beame and Fich [STOC'02] give a predecessor search time of O(lg l/lg lg l) using quadratic space.

We also show a tight Ω(lg lg n) lower bound for 2-dimensional range queries, via a new reduction. This holds even in rank space, where no superconstant lower bound was known, neither randomized nor worst-case. We also slightly improve the best lower bound for the approximate nearest neighbor problem, when small space is available.

REFERENCES

• 1: M. Ajtai. A lower bound for finding predecessors in Yao's cell probe model. Combinatorica, 8(3):235--247, 1988.
• 2: S. Alstrup , G. Stolting Brodal , T. Rauhe, New data structures for orthogonal range searching, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.198, November 12-14, 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, 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: 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]
• 8: Ding Liu, A strong lower bound for approximate nearest neighbor searching, Information Processing Letters, v.92 n.1, p.23-29, 16 October 2004 [doi>10.1016/j.ipl.2004.06.001]
• 9: 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]
• 10: 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]
• 11: Mihai Patrascu , Mikkel Thorup, Higher Lower Bounds for Near-Neighbor and Further Rich Problems, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.646-654, October 21-24, 2006 [doi>10.1109/FOCS.2006.35]
• 12: Mihai Pătraşcu , Mikkel Thorup, Time-space trade-offs for predecessor search, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132551]
• 13: 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.
• 14: 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.
• 15: D. E. Willard. Log-logarithmic worst-case range queries are possible in space Θ(N). Information Processing Letters, 17(2):81--84, 1983.
• 16: A. C.-C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th IEEE Symposium on Foundations of Computer Science (FOCS), pages 222--227, 1977.