Andrew C. Yao
ABSTRACT
In this paper, we raise and investigate the question of (storage) space- (retrieval) time tradeoff for a static database, in the general framework of Fredman's. As will be seen, such tradeoff results also lead to lower bounds on the complexity of processing a sequence of m INSERT and QUERY instructions. The latter results are incomparable to Fredman's, since the presence of DELETE instructions was crucial for his proof technique. We will present our results in detail in the next few sections. Here we will only mention three main conclusions. Firstly, circular query is shown to be intrinsically hard in the sense that, for some static database with n records, there is a space-time tradeoff TS > n1 + ε where ε>0; in contrast, orthogonal query can always be implemented with space S=0(n(log n)k) and time T=0((log n)k) for fixed k. Furthermore, any algorithm for processing 0(n) INSERT and QUERY instructions must use time Ω(n1+ε) in the worst case. Secondly, for the “interval” query, we have determined the space-time tradeoff quite precisely to be T @@@@ α(S,n), where α is the inverse to an Ackermann's function first defined by Tarjan [9]. This is a rare case where the function α arises outside the context of path compression, and is obtained through a totally independent derivation. Thirdly, we prove that, for the interval query, any algorithm to process a sequence of 0(n) INSERT and QUERY must take time Ω((n log n)/(log log n)) in the worst case. This means that one cannot hope to maintain the most efficient static data structure (with retrieval time α(S,n)) in the dynamic case.
- 1.J.L. Bentley and H.A. Mauer, "Efficient worst-case data structure for range searching," Acta Informatica 13 (1980), 155-168.Google Scholar
Digital Library
- 2.J.L. Bentley and H.A. Mauer, "A note on Euclidean near neighbor searching in the plane," Information Processing Letters 8 (1979), 133-136.Google ScholarCross Ref
- 3.M.L. Fredman, "Lower bounds on the complexity of some optimal data structures," SIAM J. on Computing 10 (1981), 1-10.Google ScholarDigital Library
- 4.M.L. Fredman, "The complexity of maintaining an array and computing its partial sums," to appear in Journal of ACM. Google ScholarDigital Library
- 5.M.L. Fredman, "Query time versus redundancy trade-offs for range queries," to appear in Journal of Computer and System Sciences, 1981.Google Scholar
- 6.M.L. Fredman, "The inherent complexity of dynamic data structures which accomodata range queries," Proc. 21st Annual IEEE Symposium on Foundations of Computer Science (1980), 191-200.Google ScholarDigital Library
- 7.G.S. Leuker, "A data structure for orthogonal range queries," Proc. 19th Annual IEEE Symposium on Foundation of Computer Science (1978), 28-34.Google ScholarDigital Library
- 8.R.L. Rivest, "Partial match retrieval algorithms," SIAM J.on Computing 5(1976), 19-50.Google ScholarDigital Library
- 9.R.E. Tarjan, "Efficiency of a good but not linear set union algorithm," Journal of ACM 22 (1975), 215-225. Google ScholarDigital Library
- 10.R.E. Tarjan, "Complexity of monotone networks for computing conjunctions," Algorithmic Aspects of Combinatorics edited by B. Alspach, P. Hell, and D.J. Miller, North-Holland (1978), 121-134.Google Scholar
- 11.D.E. Willard, "Polygon retrieval," to appear in SIAM J. on Computing.Google Scholar
- 12.D.E. Willard, "New data structures for orthogonal range queries," Tech Report TR-22-78, (1978), Aiken Computation Lab., Harvard University.Google Scholar
- 13.A.C. Yao, "On the complexity of maintaining partial sums," IBM San Jose Research Center Report RJ3228, September 1981.Google Scholar
- 14.A.C. Yao, "On the complexity of answering circular range queries," to appear as an IBM report.Google Scholar
Index Terms
- Space-time tradeoff for answering range queries (Extended Abstract)
Recommendations
Super-linear time-space tradeoff lower bounds for randomized computation
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer ScienceWe prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques ...
Near-optimal time-space tradeoff for element distinctness
SFCS '88: Proceedings of the 29th Annual Symposium on Foundations of Computer ScienceIt was conjectured by A. Borodin et al. that to solve the element distinctness problem requires TS= Omega (n/sup 2/) on a comparison-based branching program using space S and time T, which, if true, would be close to optimal since TS=O(n/sup 2/ log n) ...
Cache-oblivious range reporting with optimal queries requires superlinear space
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometryWe consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(logBN + K/B) block ...
Comments