Query time versus redundancy trade-offs for range queries

DOI10.1016/0022-0000(81)90071-4MaRDI QIDQ800105zbMATH OpenOpenAlexFDO

Authors Michael L. Fredman, Dennis James Volper

Publication date 1981

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(81)90071-4

zbMATH Keywords

binary treedata structuresdegree of redundancyquery timerange query problem

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Review text

Let S be a commutative semi-group. Let \(A(1),A(2),...,A(n)\) be an array which stores values in S. The problem is to find data structures for representing A(i) such that the range query problem \[ Return\sum^{k}_{i=j}A(i)\quad (1\leq j\leq k\leq n) \] can be efficiently implemented. The trade-offs between the degree of redundancy \({\mathcal P}\) of A(i) and the query time t in a large class of possible data structures is investigated in this paper. These concepts are formally defined. The authors then show that \({\mathcal P}+t=\Omega (\log n)\) for any data structure in the class. This shows that it is near optimal to consider the natural data structure of a minimal height binary tree with n leaves where in the ith node is stored not only the value A(i) but also the sum of the values A(j) stored in the leaves of the subtree beneath that node; the degree of redundancy here is \(\log_ 2 n\). The authors also show that the above result is best possible.

Recommendations

• Semi-group range sum revisited: query-space lower bound tightened
• Space-Time Trade-Offs for Orthogonal Range Queries
• On the Complexity of Maintaining Partial Sums
• The cell probe complexity of succinct data structures
• Lower bounds for orthogonal range searching: part II. The arithmetic model

Cites work

• A Lower Bound on the Complexity of Orthogonal Range Queries
• Inherent complexity trade-offs for range query problems
• Lower Bounds on the Complexity of Some Optimal Data Structures

Cited in

(5)

• Semi-group range sum revisited: query-space lower bound tightened
• Range selection and predecessor queries in data aware space and time
• On the Complexity of Maintaining Partial Sums
• scientific article; zbMATH DE number 2230258 (Why is no real title available?)
• On the time-space complexity of reachability queries for preprocessed graphs

This page was built for publication: Query time versus redundancy trade-offs for range queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800105)