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.3131213e-05
Overall Rank: 8,499 | 43.04%
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,771	CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models	2024	SIGMOD	5.115551e-05
10,584	Sublime: Sublinear Error & Space for Unbounded Skewed Streams	2026	SIGMOD	4.9605343e-05
11,130	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.9605343e-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.00061463175
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036097627
432	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018400309
1,070	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.0001215545
1,329	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011013041
1,444	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010616242
1,615	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	0.00010054378
2,749	Sketching Probabilistic Data Streams	2007	SIGMOD	8.0426455e-05
3,090	Persistent Data Sketching	2015	SIGMOD	7.6420011e-05
3,105	A Learned Sketch for Subgraph Counting	2021	SIGMOD	7.6278115e-05
3,214	Frequency Estimation under Local Differential Privacy	2021	VLDB	7.5121512e-05
3,282	Estimating Cardinalities with Deep Sketches	2019	SIGMOD	7.4491295e-05
3,709	Stable Learned Bloom Filters for Data Streams	2020	VLDB	7.0586477e-05
3,887	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.9277708e-05
3,931	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.900756e-05
4,744	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.4278327e-05
5,029	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.2952031e-05
5,399	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.1336701e-05
6,640	SKT: A One-Pass Multi-Sketch Data Analytics Accelerator	2021	VLDB	5.7085404e-05
7,030	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.6006602e-05
7,951	Tornado: A Distributed Spatio-Textual Stream Processing System	2015	VLDB	5.4028095e-05
8,574	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.297131e-05
8,705	Prompt: Dynamic Data-Partitioning for Distributed Micro-batch Stream Processing Systems	2020	SIGMOD	5.2707935e-05

Semantically Similar Papers

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