Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation

Summary: A sketch for disaggregated subset sum and heavy-hitter estimation, unbiased, high-accuracy sums under arbitrary filters. i.i.d. data: consistent heavy-hitter proportions; non-iid: outperforms uniform sampling, rivals priority sampling, with distributed extensions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hbdfec118d856e282
Venue: SIGMOD
Year: 2018
Pagerank: 7.8378935e-05
Overall Rank: 2,931 | 80.31%
DOI: 10.1145/3183713.3183759

Incoming Non-self Citations Over Time

Authors

1. Daniel Ting (Tableau Research)

BibTeX Citation

@inproceedings{ting_sigmod18,
        title = {{Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation}},
        author = {Ting, Daniel},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3183759},
        url = {https://dl.acm.org/doi/10.1145/3183713.3183759},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010572023
3,981	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	6.875616e-05
6,124	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.8769926e-05
7,183	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.5902277e-05
7,643	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	5.4747961e-05
7,703	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4728588e-05
7,878	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	5.4332155e-05
8,024	LadderFilter: Filtering Infrequent Items with Small Memory and Time Overhead	2023	SIGMOD	5.4035905e-05
8,042	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	5.3999898e-05
8,783	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.2776273e-05
9,520	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.1683226e-05
9,739	CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models	2024	SIGMOD	5.1325223e-05
10,345	Adaptive threshold sampling	2022	SIGMOD	5.0171283e-05
11,123	Pandora: An Efficient and Rapid Solution for Persistence-Based Tasks in High-Speed Data Streams	2025	SIGMOD	4.9769913e-05
11,544	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.9769913e-05
11,877	MinMax Sampling: A Near-optimal Global Summary for Aggregation in the Wide Area	2022	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030586757
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028621958
456	Mergeable Summaries	2012	PODS	0.00017904764
749	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014261044
911	Finding Frequent Items in Data Streams	2008	VLDB	0.0001312057
5,503	Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams	2016	SIGMOD	6.1005523e-05
7,977	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS	5.4124298e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,124	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD
2	3,928	Statistical Analysis of Sketch Estimators	2007	SIGMOD
3	8,845	On the algebra of data sketches	2021	VLDB
4	843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
5	12,602	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
6	11,544	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
7	7,977	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS
8	3,039	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
9	3,540	Tighter Estimation using Bottom k Sketches	2008	VLDB
10	12,834	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB