2011/06/23 by Gonzalo Navarro, Yakov Nekrich, Navarro, Gonzalo +3
Computer Science · #Advanced Database Systems and Queries #Computational Geometry (cs.CG) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1106.4649
openalex publication_date 2011/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider various data-analysis queries on two-dimensional points. We give new space/time tradeoffs over previous work on geometric queries such as dominance and rectangle visibility, and on semigroup and group queries such as sum, average, variance, minimum and maximum. We also introduce new solutions to queries less frequently considered in the literature such as two-dimensional quantiles, majorities, successor/predecessor, mode, and various top-k queries, considering static and dynamic scenarios.