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: hd2b06a6682e4b58b
Venue: SIGMOD
Year: 2023
Pagerank: 5.330748e-05
Overall Rank: 8,484 | 42.98%
DOI: 10.1145/3588910

Incoming Non-self Citations Over Time

Authors

1. Zirui Liu (Peking University)
2. Yixin Zhang (Peking University)
3. Yifan Zhu (Peking University)
4. Ruwen Zhang (Peking University)
5. Tong Yang (Peking University; Peng Cheng Laboratory)
6. Kun Xie (Hunan University)
7. Sha Wang (National University of Defense Technology)
8. Tao Li (National University of Defense Technology)
9. Bin Cui (Peking University)

BibTeX Citation

@inproceedings{liu_sigmod23,
        title = {{TreeSensing: Linearly Compressing Sketches with Flexibility}},
        author = {Liu, Zirui and Zhang, Yixin and Zhu, Yifan and Zhang, Ruwen and Yang, Tong and Xie, Kun and Wang, Sha and Li, Tao and Cui, Bin},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588910},
        url = {https://dl.acm.org/doi/10.1145/3588910},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,739	CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models	2024	SIGMOD	5.1325223e-05
10,518	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD	4.9769913e-05
11,069	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.9769913e-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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035962466
429	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018445263
1,067	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012187242
1,320	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011040663
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010572023
1,614	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	0.00010067153
2,738	Sketching Probabilistic Data Streams	2007	SIGMOD	8.0692701e-05
3,082	Persistent Data Sketching	2015	SIGMOD	7.6626082e-05
3,161	A Learned Sketch for Subgraph Counting	2021	SIGMOD	7.5771609e-05
3,205	Frequency Estimation under Local Differential Privacy	2021	VLDB	7.5370735e-05
3,272	Estimating Cardinalities with Deep Sketches	2019	SIGMOD	7.4711788e-05
3,701	Stable Learned Bloom Filters for Data Streams	2020	VLDB	7.0820503e-05
3,873	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.9507449e-05
3,928	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9160175e-05
5,006	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.3159614e-05
5,048	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.2971455e-05
5,379	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.1540191e-05
7,218	SKT: A One-Pass Multi-Sketch Data Analytics Accelerator	2021	VLDB	5.5810969e-05
7,703	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4728588e-05
7,937	Tornado: A Distributed Spatio-Textual Stream Processing System	2015	VLDB	5.4207339e-05
8,686	Prompt: Dynamic Data-Partitioning for Distributed Micro-batch Stream Processing Systems	2020	SIGMOD	5.2882799e-05
9,520	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.1683226e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,959	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD
2	8,500	Tree-Encoded Bitmaps	2020	SIGMOD
3	11,069	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB
4	9,268	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS
5	7,643	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB
6	8,845	On the algebra of data sketches	2021	VLDB
7	1,614	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB
8	3,514	Sketching Linear Classifiers over Data Streams	2018	SIGMOD
9	3,873	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD
10	1,170	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS