Inherent complexity trade-offs for range query problems

DOI10.1016/0304-3975(81)90099-2zbMath0522.68090OpenAlexW2021182002MaRDI QIDQ1056239

Walter A. Burkhard, Daniel J. Kleitman, Michael L. Fredman

Publication date: 1981

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(81)90099-2

zbMATH Keywords

average complexitiesinherent trade-offsrange query problemsretrieve transactionsupdate transactions

Mathematics Subject Classification ID

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

Related Items (6)

Lower bounds on zero-one matrices. ⋮ How hard is half-space range searching? ⋮ Lower Bounds on the Complexity of Polytope Range Searching ⋮ Partial sums on the ultra-wide word RAM ⋮ Unnamed Item ⋮ Query time versus redundancy trade-offs for range queries

Cites Work

• Lower Bounds on the Complexity of Some Optimal Data Structures
• A Lower Bound on the Complexity of Orthogonal Range Queries
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• Some Monotonicity Properties of Partial Orders

This page was built for publication: Inherent complexity trade-offs for range query problems