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: 6621
Venue: SIGMOD
Year: 2023
Pagerank: 5.4556836e-05
Overall Rank: 8,310 | 42.99%
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,556	CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models	2024	SIGMOD	5.2528121e-05
10,295	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD	5.093636e-05
10,613	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	5.093636e-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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
1,499	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010564536
1,644	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	0.00010132912
2,697	Sketching Probabilistic Data Streams	2007	SIGMOD	8.2451054e-05
3,023	Persistent Data Sketching	2015	SIGMOD	7.8398269e-05
3,143	Frequency Estimation under Local Differential Privacy	2021	VLDB	7.7137142e-05
3,213	Estimating Cardinalities with Deep Sketches	2019	SIGMOD	7.6328677e-05
3,283	A Learned Sketch for Subgraph Counting	2021	SIGMOD	7.56675e-05
4,073	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.9242783e-05
4,083	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.9160949e-05
4,142	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.8764637e-05
4,900	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.4534715e-05
5,184	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3283918e-05
5,255	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.2982495e-05
7,069	SKT: A One-Pass Multi-Sketch Data Analytics Accelerator	2021	VLDB	5.7117595e-05
7,794	Tornado: A Distributed Spatio-Textual Stream Processing System	2015	VLDB	5.5429908e-05
8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4853605e-05
8,568	Prompt: Dynamic Data-Partitioning for Distributed Micro-batch Stream Processing Systems	2020	SIGMOD	5.4118703e-05
9,329	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.2894515e-05

Semantically Similar Papers

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