2006/09/07 by Šumit Ganguly, Sumit Ganguly, Ganguly, Sumit +2 · 1 citation
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0609032
11 pages
openalex publication_date 2006/09/07 · arxiv created 2006/10/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present the \crprecis structure, that is a general-purpose, deterministic and sub-linear data structure for summarizing update data streams. The \crprecis structure yields the first deterministic sub-linear space/time algorithms for update streams for answering a variety of fundamental stream queries, such as, (a) point queries, (b) range queries, (c) finding approximate frequent items, (d) finding approximate quantiles, (e) finding approximate hierarchical heavy hitters, (f) estimating inner-products, (g) near-optimal B-bucket histograms, etc..