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: 6560
Venue: SIGMOD
Year: 2023
Pagerank: 4.3997447e-05
Overall Rank: 9,041 | 37.17%
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,408	CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models	2024	SIGMOD	4.3399748e-05
10,327	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.1905499e-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.00059446482
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
1,394	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012218557
1,586	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011245213
1,970	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	9.9024431e-05
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
2,540	Frequency Estimation under Local Differential Privacy	2021	VLDB	8.5714554e-05
3,047	Sketching Probabilistic Data Streams	2007	SIGMOD	7.6537004e-05
3,618	Persistent Data Sketching	2015	SIGMOD	6.9080647e-05
3,725	Estimating Cardinalities with Deep Sketches	2019	SIGMOD	6.8117015e-05
3,781	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7691344e-05
3,810	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.7375383e-05
4,239	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.3273184e-05
4,448	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.1741316e-05
5,636	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	5.3985928e-05
5,886	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2847297e-05
5,910	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	5.2718714e-05
7,163	SKT: A One-Pass Multi-Sketch Data Analytics Accelerator	2021	VLDB	4.808534e-05
8,018	Tornado: A Distributed Spatio-Textual Stream Processing System	2015	VLDB	4.6014254e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5552628e-05
8,594	Prompt: Dynamic Data-Partitioning for Distributed Micro-batch Stream Processing Systems	2020	SIGMOD	4.4844961e-05
9,230	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	4.3650857e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,347	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD	4.7502395e-05
8,424	Tree-Encoded Bitmaps	2020	SIGMOD	4.5111681e-05
10,327	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.1905499e-05
8,932	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS	4.4229886e-05
8,246	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	4.5462498e-05
8,446	On the algebra of data sketches	2021	VLDB	4.5042806e-05
1,970	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	9.9024431e-05
3,322	Sketching Linear Classifiers over Data Streams	2018	SIGMOD	7.217965e-05
3,810	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.7375383e-05
922	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00015254436