Persistent Bloom Filter: Membership Testing for the Entire History

Summary: Introduces persistent Bloom Filter (PBF) for temporal membership testing across history. Unlike standard Bloom Filters that scale poorly for temporal queries, PBF encodes presence over time in compact space to support fast history-wide membership tests. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5519
Venue: SIGMOD
Year: 2018
Pagerank: 6.4195676e-05
Overall Rank: 4,971 | 65.90%
DOI: 10.1145/3183713.3183737

Incoming Non-self Citations Over Time

Authors

1. Yanqing Peng (University of Utah)
2. Jinwei Guo (East China Normal University)
3. Feifei Li (University of Utah)
4. Weining Qian (East China Normal University)
5. Aoying Zhou (East China Normal University)

BibTeX Citation

@inproceedings{peng_sigmod18,
        title = {{Persistent Bloom Filter: Membership Testing for the Entire History}},
        author = {Peng, Yanqing and Guo, Jinwei and Li, Feifei and Qian, Weining and Zhou, Aoying},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3183737},
        url = {https://dl.acm.org/doi/10.1145/3183713.3183737},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,698	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.2450522e-05
3,898	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	7.0367583e-05
5,255	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.2982495e-05
6,685	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	5.8034001e-05
7,036	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.7212447e-05
7,716	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	5.5605526e-05
11,423	A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data Streams	2023	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
681	Access Methods For Multiversion Data	1989	SIGMOD	0.0001502579
862	Spectral Bloom Filters	2003	SIGMOD	0.00013532857
1,126	Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia	2013	VLDB	0.00012078607
1,210	Immortal DB: Transaction Time Support for SQL Server	2005	SIGMOD	0.00011656235
3,023	Persistent Data Sketching	2015	SIGMOD	7.8398269e-05
3,038	Skippy: a New Snapshot Indexing Method for Time Travel in the Storage Manager	2008	SIGMOD	7.8272965e-05
3,691	Searching in Time	2006	SIGMOD	7.1998478e-05
7,936	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.5181056e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,612	Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying	2021	SIGMOD
2	4,532	Stacked Filters: Learning to Filter by Structure	2021	VLDB
3	11,572	New Wine in an Old Bottle: Data-Aware Hash Functions for Bloom Filters	2022	VLDB
4	7,469	Optimizing Collections of Bloom Filters within a Space Budget	2024	VLDB
5	7,776	Aleph Filter: To Infinity in Constant Time	2024	VLDB
6	3,533	Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters	2006	SIGMOD
7	6,539	Prefix Filter: Practically and Theoretically Better Than Bloom	2022	VLDB
8	862	Spectral Bloom Filters	2003	SIGMOD
9	8,408	A Shifting Bloom Filter Framework for Set Queries	2016	VLDB
10	4,073	Stable Learned Bloom Filters for Data Streams	2020	VLDB