Database Paper Browser

Back to papers

Mergeable Summaries

Summary: Show heavy-hitter and quantile summaries can be made mergeable: deterministic heavy-hitters size O(1/ε) and randomized fully-mergeable quantiles size O((1/ε)log^{3/2}(1/ε)). Extend to geometric ε-approximations/ε-kernels and show MG=SpaceSaving. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1562
Venue
PODS
Year
2012
Pagerank
0.00024196343
Overall Rank
402 | 97.21%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 50 citing papers.

Rank Citing Paper Year Venue Pagerank
2,752 Composable Core-sets for Diversity and Coverage Maximization 2014 PODS 8.1742326e-05
2,843 A General-Purpose Counting Filter: Making Every Bit Count 2017 SIGMOD 8.0257314e-05
2,914 DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees 2019 VLDB 7.9118579e-05
2,953 Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries 2018 VLDB 7.8267643e-05
3,271 Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation 2018 SIGMOD 7.2968732e-05
3,503 FREDE: Anytime Graph Embeddings 2021 VLDB 7.0355661e-05
3,558 Approximate Selection with Guarantees using Proxies 2020 VLDB 6.9765724e-05
3,922 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 6.6291079e-05
4,076 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 6.4680854e-05
4,190 Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks 2012 PODS 6.3739017e-05
4,966 Relative Error Streaming Quantiles 2021 PODS 5.7959749e-05
5,131 Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch 2023 PODS 5.6751843e-05
5,550 Optimal Bounds for Approximate Counting 2022 PODS 5.4422275e-05
5,627 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 5.403782e-05
5,909 At-the-time and Back-in-time Persistent Sketches 2021 SIGMOD 5.2769377e-05
5,956 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS 5.2566971e-05
5,971 Optimal and General Out-of-Order Sliding-Window Aggregation 2019 VLDB 5.2480159e-05
6,298 Hillview: A trillion-cell spreadsheet for big data 2019 VLDB 5.1226987e-05
6,602 Continuous Matrix Approximation on Distributed Data 2014 VLDB 4.9971153e-05
6,740 Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing 2021 SIGMOD 4.944395e-05
6,774 Matrix Sketching Over Sliding Windows 2016 SIGMOD 4.9299348e-05
7,534 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 4.7180004e-05
7,949 Efficient Matrix Sketching over Distributed Data 2017 PODS 4.613363e-05
8,062 Together is Better: Heavy Hitters Quantile Estimation 2023 SIGMOD 4.5943269e-05
8,203 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 4.5596344e-05
8,393 LAQy: Efficient and Reusable Query Approximations via Lazy Sampling 2023 SIGMOD 4.5280102e-05
8,451 Efficient framework for operating on data sketches 2023 VLDB 4.5086031e-05
8,452 On the algebra of data sketches 2021 VLDB 4.5086031e-05
8,522 Differentially Private Hierarchical Heavy Hitters 2024 PODS 4.4937074e-05
8,535 Biclustering and Boolean Matrix Factorization in Data Streams 2020 VLDB 4.4937074e-05
8,594 Stream Frequency over Interval Queries 2019 VLDB 4.4891331e-05
8,673 CoopStore: Optimizing Precomputed Summaries for Aggregation 2020 VLDB 4.4709116e-05
8,717 Scotch: Generating FPGA-Accelerators for Sketching at Line Rate 2021 VLDB 4.4614498e-05
9,211 Optimistic Data Parallelism for FPGA-Accelerated Sketching 2023 VLDB 4.3726511e-05
9,237 Determining Exact Quantiles with Randomized Summaries 2024 SIGMOD 4.3690661e-05
10,113 SplineSketch: Even More Accurate Quantiles with Error Guarantees 2026 SIGMOD 4.1945683e-05
10,198 Quantile Estimation with Duplicates 2026 SIGMOD 4.1945683e-05
10,388 Randomized Sketches for Quantile in LSM-tree based Store 2025 SIGMOD 4.1945683e-05
10,404 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.1945683e-05
10,659 Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing 2025 VLDB 4.1945683e-05
10,710 Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach 2025 VLDB 4.1945683e-05
10,927 Computing A Well-Representative Summary of Conjunctive Query Results 2024 PODS 4.1945683e-05
11,169 Applications of Sketching and Pathways to Impact 2023 PODS 4.1945683e-05
11,261 Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions 2023 VLDB 4.1945683e-05
11,358 Scaling Equi-Joins 2022 SIGMOD 4.1945683e-05
11,371 Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments 2022 VLDB 4.1945683e-05
11,434 Data-Independent Space Partitionings for Summaries 2021 PODS 4.1945683e-05
11,502 In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All 2021 VLDB 4.1945683e-05
11,505 Approximating Median Absolute Deviation with Bounded Error 2021 VLDB 4.1945683e-05
11,901 Compact Summaries over Large Datasets 2015 PODS 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Previous Page 1 / 1 Next

Semantically Similar Papers