2020/02/08 by Edward Gan, Gan, Edward, Peter Bailis +3
Computer Science · #Advanced Database Systems and Queries #Aggregate (composite) #Automatic summarization #Computer science #Data Management and Algorithms #Data mining #Databases (cs.DB) #FOS: Computer and information sciences #Information retrieval #Partition (number theory) #Raw data #Semantic Web and Ontologies #Statistic #Statistics #Storyboard #cs.DB
paper · pdf · doi:10.48550/arxiv.2002.03063
arxiv created 2020/02/08 · openalex publication_date 2020/02/08 · arxiv updated 2020/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An emerging class of data systems partition their data and precompute approximate summaries (i.e., sketches and samples) for each segment to reduce query costs. They can then aggregate and combine the segment summaries to estimate results without scanning the raw data. However, given limited storage space each summary introduces approximation errors that affect query accuracy. For instance, systems that use existing mergeable summaries cannot reduce query error below the error of an individual precomputed summary. We introduce Storyboard, a query system that optimizes item frequency and quantile summaries for accuracy when aggregating over multiple segments. Compared to conventional mergeable summaries, Storyboard leverages additional memory available for summary construction and aggregation to derive a more precise combined result. This reduces error by up to 25x over interval aggregations and 4.4x over data cube aggregations on industrial datasets compared to standard summarization methods, with provable worst-case error guarantees.