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

DOI10.1007/s00453-017-0307-3zbMath1435.68071OpenAlexW2605208448MaRDI QIDQ1751095

Yi Yang, Xiaocheng Hu, Yufei Tao, 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

semigrouplower boundlength-decomposition propertyrange-sum queries

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Tight lower bounds for halfspace range searching
• Optimal partition trees
• Range searching with efficient hierarchical cuttings
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• A Lower Bound on the Complexity of Orthogonal Range Queries
• Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums
• The cell probe complexity of dynamic range counting
• On Range Searching in the Group Model and Combinatorial Discrepancy