Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying

Summary: Introduces Circular Shift and Coalesce (CSC) to support approximate MS-MMQ by packing n sets into a single compact sketch instead of per-set MQs. Queries read only a few bytes to return all containing sets, delivering major memory and speedups (up to 91x faster, 49x more accurate) and compatibility with standard MQ structures like Bloom filters. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6109
Venue: SIGMOD
Year: 2021
Pagerank: 4.4801584e-05
Overall Rank: 8,634 | 39.94%
DOI: 10.1145/3448016.3452829

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,732	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	4.6657123e-05
8,250	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	4.5506131e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
102	The Case for Learned Index Structures	2018	SIGMOD	0.00049545203
781	Spectral Bloom Filters	2003	SIGMOD	0.00016741046
1,248	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.00013046661
2,471	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	8.7320072e-05
3,838	Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters	2006	SIGMOD	6.7134945e-05
8,178	A Shifting Bloom Filter Framework for Set Queries	2016	VLDB	4.5672537e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,779	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.1320575e-05
4,485	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.1458149e-05
2,843	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	8.0257314e-05
9,552	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	4.3254416e-05
11,222	A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data Streams	2023	SIGMOD	4.1945683e-05
6,831	Prefix Filter: Practically and Theoretically Better Than Bloom	2022	VLDB	4.9130458e-05
2,464	Fast Set Intersection in Memory	2011	VLDB	8.7524354e-05
5,596	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	5.4181535e-05
8,697	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	4.4657888e-05
8,178	A Shifting Bloom Filter Framework for Set Queries	2016	VLDB	4.5672537e-05