Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items

Summary: Proposes Double-Anonymous sketch to compute global top-K across disjoint streams with top-K-fairness. Leverages double-anonymity, hot panning, and early freezing; provides theoretical guarantees and extensive experiments showing substantial error reductions vs state-of-the-art; open-source code. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6582
Venue: SIGMOD
Year: 2023
Pagerank: 4.6657123e-05
Overall Rank: 7,732 | 46.22%
DOI: 10.1145/3588933

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,034	SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation	2026	SIGMOD	4.1945683e-05
10,315	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
1,584	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011255801
2,471	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	8.7320072e-05
2,607	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.4630211e-05
2,843	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	8.0257314e-05
3,271	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.2968732e-05
3,319	Sketching Linear Classifiers over Data Streams	2018	SIGMOD	7.226439e-05
3,614	Persistent Data Sketching	2015	SIGMOD	6.9147318e-05
3,751	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	6.7888099e-05
3,778	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7747398e-05
3,824	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	6.7260705e-05
4,378	Fast Processing and Querying of 170TB of Genomics Data via a Repeated And Merged BloOm Filter (RAMBO)	2021	SIGMOD	6.2404547e-05
5,163	Finding Persistent Items in Data Streams	2017	VLDB	5.6550193e-05
5,332	Persistent Bloom Filter: Membership Testing for the Entire History	2018	SIGMOD	5.5662513e-05
5,369	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	5.5434712e-05
5,496	Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams	2016	SIGMOD	5.4757316e-05
5,516	Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design	2021	SIGMOD	5.4628856e-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
6,085	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD	5.2195267e-05
6,593	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	4.9999287e-05
8,502	Conditional Cuckoo Filters	2021	SIGMOD	4.4972336e-05
8,634	Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying	2021	SIGMOD	4.4801584e-05
8,635	Bidirectionally Densifying LSH Sketches with Empty Bins	2021	SIGMOD	4.4801584e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,198	Quantile Estimation with Duplicates	2026	SIGMOD	4.1945683e-05
4,979	Fast Data Anonymization with Low Information Loss	2007	VLDB	5.7878768e-05
7,276	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.7798595e-05
1,584	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011255801
3,665	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB	6.8633354e-05
9,082	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	4.3998984e-05
6,905	PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy	2021	VLDB	4.8925595e-05
5,369	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	5.5434712e-05
2,894	Pan-private Algorithms Via Statistics on Sketches	2011	PODS	7.9474698e-05
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05