×

Lower bounds for dynamic range query problems that permit subtraction. (English) Zbl 0596.68066

Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 444-453 (1986).
Summary: [For the entire collection see Zbl 0587.00019.]
Fredman has shown that \(\Omega (\log^ kN)\) lower bounds the complexity for doing aggregate orthogonal range queries on a set of N records in a dynamic environment, where the computing machine can use only addition for calculating aggregates. We show that a natural generalization of R. G. Karlsson, J. I. Munro, and E. L. Robertson’s [Lect. Notes Comput. Sci. 194, 318-327 (1985; Zbl 0575.68063)] contiguous segment assumption extends Fredman’s formalism so that subtraction as well as addition may be included in the \(\Omega (\log^ kN)\) lower bound.

MSC:

68P20 Information storage and retrieval of data
68Q25 Analysis of algorithms and problem complexity
68P10 Searching and sorting