Semi-group range sum revisited: query-space lower bound tightened

DOI10.1007/S00453-017-0307-3MaRDI QIDQ1751095zbMATH OpenOpenAlexFDO

Authors Xiaocheng Hu, Yufei Tao, Yi Yang, Shuigeng Zhou

Publication date 23 May 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-017-0307-3

zbMATH Keywords

lower boundsemigrouplength-decomposition propertyrange-sum queries

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General structure theory for semigroups (20M10)

Recommendations

• Query time versus redundancy trade-offs for range queries
• Tight lower bounds for halfspace range searching
• Tight lower bounds for halfspace range searching
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• On space efficient two dimensional range minimum data structures

Cites work

• scientific article; zbMATH DE number 5485435 (Why is no real title available?)
• A Lower Bound on the Complexity of Orthogonal Range Queries
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• On range searching in the group model and combinatorial discrepancy
• Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums
• Optimal partition trees
• Range searching with efficient hierarchical cuttings
• The cell probe complexity of dynamic range counting
• Tight lower bounds for halfspace range searching

Cited in

(2)

• Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model
• Query time versus redundancy trade-offs for range queries

This page was built for publication: Semi-group range sum revisited: query-space lower bound tightened

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