Space-time tradeoff for answering range queries (Extended Abstract)

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 -&-gt; n1 + -&-egr; where -&-egr;-&-gt;0; in contrast, orthogonal query can always be implemented with space S-&-equil;0(n(log n)k) and time T-&-equil;0((log n)k) for fixed k. Furthermore, any algorithm for processing 0(n) INSERT and QUERY instructions must use time -&-Ohgr;(n1+-&-egr;) in the worst case. Secondly, for the -&-ldquo;interval-&-rdquo; query, we have determined the space-time tradeoff quite precisely to be T @@@@ -&-agr;(S,n), where -&-agr; is the inverse to an Ackermann's function first defined by Tarjan [9]. This is a rare case where the function -&-agr; 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 -&-Ohgr;((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 -&-agr;(S,n)) in the dynamic case.

REFERENCES

• 1: J.L. Bentley and H.A. Mauer, "Efficient worst-case data structure for range searching," Acta Informatica 13 (1980), 155-168.
• 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.
• 3: M.L. Fredman, "Lower bounds on the complexity of some optimal data structures," SIAM J. on Computing 10 (1981), 1-10.
• 4: Michael L. Fredman, The Complexity of Maintaining an Array and Computing Its Partial Sums, Journal of the ACM (JACM), v.29 n.1, p.250-260, Jan. 1982 [doi>10.1145/322290.322305]
• 5: M.L. Fredman, "Query time versus redundancy trade-offs for range queries," to appear in Journal of Computer and System Sciences, 1981.
• 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.
• 7: G.S. Leuker, "A data structure for orthogonal range queries," Proc. 19th Annual IEEE Symposium on Foundation of Computer Science (1978), 28-34.
• 8: R.L. Rivest, "Partial match retrieval algorithms," SIAM J.on Computing 5(1976), 19-50.
• 9: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 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.
• 11: D.E. Willard, "Polygon retrieval," to appear in SIAM J. on Computing.
• 12: D.E. Willard, "New data structures for orthogonal range queries," Tech Report TR-22-78, (1978), Aiken Computation Lab., Harvard University.
• 13: A.C. Yao, "On the complexity of maintaining partial sums," IBM San Jose Research Center Report RJ3228, September 1981.
• 14: A.C. Yao, "On the complexity of answering circular range queries," to appear as an IBM report.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Theory