Inherent complexity trade-offs for range query problems

DOI10.1016/0304-3975(81)90099-2MaRDI QIDQ1056239zbMATH OpenOpenAlexFDO

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

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

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

Cites work

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

Cited in

(6)

• How hard is half-space range searching?
• scientific article; zbMATH DE number 2230258 (Why is no real title available?)
• Lower Bounds on the Complexity of Polytope Range Searching
• Lower bounds on zero-one matrices.
• Query time versus redundancy trade-offs for range queries
• Partial sums on the ultra-wide word RAM

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

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