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)
Incoming Non-self Citations Over Time
Authors
- 1. Rundong Li (Xi'an Jiaotong University)
- 2. Pinghui Wang (Shenzhen University; Xi'an Jiaotong University)
- 3. Jiongli Zhu (Xi'an Jiaotong University)
- 4. Junzhou Zhao (Xi'an Jiaotong University)
- 5. Jia Di (Xi'an Jiaotong University)
- 6. Xiaofei Yang (Xi'an Jiaotong University)
- 7. Kai Ye (Xi'an Jiaotong University)
BibTeX Citation
@inproceedings{li_sigmod21,
title = {{Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying}},
author = {Li, Rundong and Wang, Pinghui and Zhu, Jiongli and Zhao, Junzhou and Di, Jia and Yang, Xiaofei and Ye, Kai},
series = {{SIGMOD} '21},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3448016.3452829},
url = {https://dl.acm.org/doi/10.1145/3448016.3452829},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,498 | Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation | 2022 | VLDB | 5.6031077e-05 |
| 7,716 | Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items | 2023 | SIGMOD | 5.5605526e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 43 | The Case for Learned Index Structures | 2018 | SIGMOD | 0.00046060254 |
| 789 | Don't Thrash: How to Cache Your Hash on Flash | 2012 | VLDB | 0.0001401724 |
| 862 | Spectral Bloom Filters | 2003 | SIGMOD | 0.00013532857 |
| 1,975 | Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity | 2018 | VLDB | 9.3645236e-05 |
| 3,533 | Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters | 2006 | SIGMOD | 7.3366144e-05 |
| 8,408 | A Shifting Bloom Filter Framework for Set Queries | 2016 | VLDB | 5.4312165e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,358 | Parallel Index-Based Structural Graph Clustering and Its Approximation | 2021 | SIGMOD |
| 2 | 2,043 | A General-Purpose Counting Filter: Making Every Bit Count | 2017 | SIGMOD |
| 3 | 8,477 | Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs | 2025 | SIGMOD |
| 4 | 11,423 | A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data Streams | 2023 | SIGMOD |
| 5 | 6,539 | Prefix Filter: Practically and Theoretically Better Than Bloom | 2022 | VLDB |
| 6 | 2,245 | Fast Set Intersection in Memory | 2011 | VLDB |
| 7 | 5,472 | Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps | 2006 | VLDB |
| 8 | 10,289 | Sketch-based Secure Query Processing for Streaming Data | 2026 | SIGMOD |
| 9 | 7,747 | Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries | 2024 | SIGMOD |
| 10 | 8,408 | A Shifting Bloom Filter Framework for Set Queries | 2016 | VLDB |