TreeSensing: Linearly Compressing Sketches with Flexibility

Summary: TreeSensing linearly compresses probabilistic sketches by splitting counters into small and large parts, using TreeEncoding for small counters and SketchSensing (compressive sensing) for large ones. It preserves linearity and, across 7 sketches, achieves up to 100x error reduction and 5.1x speedup vs Cluster-Reduce, with open-source code. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6559
Venue: SIGMOD
Year: 2023
Pagerank: 4.4039656e-05
Overall Rank: 9,041 | 37.11%
DOI: 10.1145/3588910

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,402	CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models	2024	SIGMOD	4.3441378e-05
10,315	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
1,392	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012229045
1,584	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011255801
1,967	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	9.9131712e-05
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
2,540	Frequency Estimation under Local Differential Privacy	2021	VLDB	8.5797299e-05
3,041	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6697078e-05
3,614	Persistent Data Sketching	2015	SIGMOD	6.9147318e-05
3,725	Estimating Cardinalities with Deep Sketches	2019	SIGMOD	6.8170734e-05
3,778	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7747398e-05
3,808	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.7455428e-05
4,237	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.3333486e-05
4,446	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.1800659e-05
5,627	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.403782e-05
5,880	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2898074e-05
5,909	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	5.2769377e-05
7,164	SKT: A One-Pass Multi-Sketch Data Analytics Accelerator	2021	VLDB	4.8131514e-05
8,073	Tornado: A Distributed Spatio-Textual Stream Processing System	2015	VLDB	4.5919735e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5596344e-05
8,596	Prompt: Dynamic Data-Partitioning for Distributed Micro-batch Stream Processing Systems	2020	SIGMOD	4.4887993e-05
9,227	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	4.3692732e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,351	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD	4.7545562e-05
8,430	Tree-Encoded Bitmaps	2020	SIGMOD	4.5154973e-05
10,315	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.1945683e-05
9,060	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS	4.4039656e-05
8,250	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	4.5506131e-05
8,452	On the algebra of data sketches	2021	VLDB	4.5086031e-05
1,967	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	9.9131712e-05
3,319	Sketching Linear Classifiers over Data Streams	2018	SIGMOD	7.226439e-05
3,808	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.7455428e-05
1,040	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00014488943