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: h515fa88b40565a5f
Venue: SIGMOD
Year: 2018
Pagerank: 6.277732e-05
Overall Rank: 5,093 | 65.76%
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,664	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.1569551e-05
3,980	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	6.8788724e-05
5,373	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	6.1569337e-05
6,816	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	5.6731874e-05
7,180	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.5928753e-05
7,873	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	5.4357887e-05
11,737	A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data Streams	2023	SIGMOD	4.9793485e-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
494	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017387321
687	Access Methods For Multiversion Data	1989	SIGMOD	0.00014763858
870	Spectral Bloom Filters	2003	SIGMOD	0.0001334417
1,117	Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia	2013	VLDB	0.00011953704
1,207	Immortal DB: Transaction Time Support for SQL Server	2005	SIGMOD	0.00011538247
3,080	Persistent Data Sketching	2015	SIGMOD	7.6662346e-05
3,097	Skippy: a New Snapshot Indexing Method for Time Travel in the Storage Manager	2008	SIGMOD	7.6524049e-05
3,757	Searching in Time	2006	SIGMOD	7.0441066e-05
8,104	Logging Every Footstep: Quantile Summaries for the Entire History	2010	SIGMOD	5.3942942e-05

Semantically Similar Papers

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