Space-Efficient Data-Analysis Queries on Grids
Gonzalo Navarro and Luís Russo
We consider various data-analysis queries on two-dimensional points.
We give new space/time tradeoffs over previous work on
semigroup and group
queries such as sum, average, variance, minimum and maximum. We also introduce
new solutions to queries rarely considered in the literature such as
two-dimensional quantiles, majorities, successor/predecessor and mode queries.
We face static and dynamic scenarios.