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

data structuresbinary treedegree of redundancyquery timerange query problem

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 2230258 (Why is no real title available?)
• On the time-space complexity of reachability queries for preprocessed graphs
• On the Complexity of Maintaining Partial Sums

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)