Inherent complexity trade-offs for range query problems

DOI10.1016/0304-3975(81)90099-2zbMATH Open0522.68090OpenAlexW2021182002MaRDI QIDQ1056239FDOQ1056239

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

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

Cited In (6)

• How hard is half-space range searching?
• Lower bounds on zero-one matrices.
• Partial sums on the ultra-wide word RAM
• Title not available (Why is that?)
• Lower Bounds on the Complexity of Polytope Range Searching
• Query time versus redundancy trade-offs for range queries

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)