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.00024383201
Overall Rank
398 | 97.24%
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,756 Composable Core-sets for Diversity and Coverage Maximization 2014 PODS 8.1682323e-05
2,848 A General-Purpose Counting Filter: Making Every Bit Count 2017 SIGMOD 8.0202739e-05
2,918 DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees 2019 VLDB 7.9043213e-05
2,954 Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries 2018 VLDB 7.8218804e-05
3,273 Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation 2018 SIGMOD 7.2899198e-05
3,404 FREDE: Anytime Graph Embeddings 2021 VLDB 7.1333873e-05
3,553 Approximate Selection with Guarantees using Proxies 2020 VLDB 6.9763548e-05
3,923 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 6.6232068e-05
4,080 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 6.4619407e-05
4,190 Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks 2012 PODS 6.3677694e-05
4,950 Optimal Bounds for Approximate Counting 2022 PODS 5.808904e-05
4,969 Relative Error Streaming Quantiles 2021 PODS 5.790405e-05
5,104 Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch 2023 PODS 5.6929767e-05
5,636 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 5.3985928e-05
5,910 At-the-time and Back-in-time Persistent Sketches 2021 SIGMOD 5.2718714e-05
5,954 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS 5.2542261e-05
6,133 Optimal and General Out-of-Order Sliding-Window Aggregation 2019 VLDB 5.1917864e-05
6,302 Hillview: A trillion-cell spreadsheet for big data 2019 VLDB 5.1166201e-05
6,603 Continuous Matrix Approximation on Distributed Data 2014 VLDB 4.9923197e-05
6,724 Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing 2021 SIGMOD 4.9449472e-05
6,775 Matrix Sketching Over Sliding Windows 2016 SIGMOD 4.9252038e-05
7,533 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 4.7134753e-05
7,952 Efficient Matrix Sketching over Distributed Data 2017 PODS 4.6089395e-05
8,066 Together is Better: Heavy Hitters Quantile Estimation 2023 SIGMOD 4.5899218e-05
8,203 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 4.5552628e-05
8,370 LAQy: Efficient and Reusable Query Approximations via Lazy Sampling 2023 SIGMOD 4.5287754e-05
8,445 Efficient framework for operating on data sketches 2023 VLDB 4.5042806e-05
8,446 On the algebra of data sketches 2021 VLDB 4.5042806e-05
8,520 Differentially Private Hierarchical Heavy Hitters 2024 PODS 4.4893996e-05
8,521 Computing A Well-Representative Summary of Conjunctive Query Results 2024 PODS 4.4893996e-05
8,534 Biclustering and Boolean Matrix Factorization in Data Streams 2020 VLDB 4.4893996e-05
8,592 Stream Frequency over Interval Queries 2019 VLDB 4.4848323e-05
8,669 CoopStore: Optimizing Precomputed Summaries for Aggregation 2020 VLDB 4.4667395e-05
8,715 Scotch: Generating FPGA-Accelerators for Sketching at Line Rate 2021 VLDB 4.4571724e-05
9,213 Optimistic Data Parallelism for FPGA-Accelerated Sketching 2023 VLDB 4.3684604e-05
9,244 Determining Exact Quantiles with Randomized Summaries 2024 SIGMOD 4.3648789e-05
10,113 SplineSketch: Even More Accurate Quantiles with Error Guarantees 2026 SIGMOD 4.1905499e-05
10,198 Quantile Estimation with Duplicates 2026 SIGMOD 4.1905499e-05
10,399 Randomized Sketches for Quantile in LSM-tree based Store 2025 SIGMOD 4.1905499e-05
10,415 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.1905499e-05
10,667 Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing 2025 VLDB 4.1905499e-05
10,717 Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach 2025 VLDB 4.1905499e-05
11,172 Applications of Sketching and Pathways to Impact 2023 PODS 4.1905499e-05
11,263 Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions 2023 VLDB 4.1905499e-05
11,360 Scaling Equi-Joins 2022 SIGMOD 4.1905499e-05
11,373 Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments 2022 VLDB 4.1905499e-05
11,437 Data-Independent Space Partitionings for Summaries 2021 PODS 4.1905499e-05
11,506 In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All 2021 VLDB 4.1905499e-05
11,509 Approximating Median Absolute Deviation with Bounded Error 2021 VLDB 4.1905499e-05
11,909 Compact Summaries over Large Datasets 2015 PODS 4.1905499e-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