Lower bound techniques for data structures
Erik D. Demaine, Mihai Pǎtraşcu · 2008
We describe new techniques for proving lower bounds on data-structure problems, with the following broad consequences: (1) the first Ω(lg n) lower bound for any dynamic problem, improving on a bound that had been standing since 1989; (2) for static data structures, the first separation between linear and polynomial space. Specifically, for some problems that have constant query time when polynomial space is allowed, we can show Ω(lg n/lg lg n) bounds when the space is O(n · polylog n). Using these techniques, we analyze a variety of central data-structure problems, and obtain improved lower bounds for the following: (1) the partial-sums problem (a fundamental application of augmented binary search trees); (2) the predecessor problem (which is equivalent to IP lookup in Internet routers); (3) dynamic trees and dynamic connectivity; (4) orthogonal range stabbing. (5) orthogonal range counting, and orthogonal range reporting; (6) the partial match problem (searching with wild-cards); (7) (1 + e)-approximate near neighbor on the hypercube; (8) approximate nearest neighbor in the e ∞ to metric. Our new techniques lead to surprisingly non-technical proofs. For several problems, we obtain simpler proofs for bounds that were already known. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)