Spectral Bloom Filters

Summary: Spectral Bloom Filters extend Bloom Filters to multisets, enabling multiplicity estimation with small error and spectrum filtering. With modest memory, they support insertions/deletions and incremental maintenance, acting as a granular histogram for queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h7049dad5626994aa
Venue: SIGMOD
Year: 2003
Pagerank: 0.0001334417
Overall Rank: 870 | 94.16%
DOI: 10.1145/872757.872787

Incoming Non-self Citations Over Time

Authors

1. Saar Cohen (Tel Aviv University)
2. Yossi Matias (Tel Aviv University)

BibTeX Citation

@inproceedings{cohen_sigmod03,
        title = {{Spectral Bloom Filters}},
        author = {Cohen, Saar and Matias, Yossi},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872787},
        url = {https://dl.acm.org/doi/10.1145/872757.872787},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,844	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	9.5159229e-05
2,071	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	9.0866982e-05
3,285	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.4559907e-05
3,547	Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters	2006	SIGMOD	7.2121974e-05
3,703	Stable Learned Bloom Filters for Data Streams	2020	VLDB	7.0842566e-05
4,734	Fast Processing and Querying of 170TB of Genomics Data via a Repeated And Merged BloOm Filter (RAMBO)	2021	SIGMOD	6.4453753e-05
4,778	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB	6.4174716e-05
4,979	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.3300966e-05
5,093	Persistent Bloom Filter: Membership Testing for the Entire History	2018	SIGMOD	6.277732e-05
5,580	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.0769576e-05
6,188	Finding Global Icebergs over Distributed Data Sets	2006	PODS	5.8571256e-05
6,936	A Shifting Bloom Filter Framework for Set Queries	2016	VLDB	5.6400144e-05
7,184	Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying	2021	SIGMOD	5.5913067e-05
8,138	Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams	2013	VLDB	5.3922449e-05
8,516	Optimistic Data Parallelism for FPGA-Accelerated Sketching	2023	VLDB	5.3250329e-05
9,258	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS	5.2056825e-05
9,509	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.1707704e-05
9,681	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1427987e-05
9,890	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.1149505e-05
10,142	A four-dimensional Analysis of Partitioned Approximate Filters	2021	VLDB	5.0734597e-05
10,453	Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor	2026	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052121228
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
344	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00020461727
588	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015906635
745	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014288286
1,203	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011548537

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,881	New Wine in an Old Bottle: Data-Aware Hash Functions for Bloom Filters	2022	VLDB
2	10,142	A four-dimensional Analysis of Partitioned Approximate Filters	2021	VLDB
3	1,117	Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia	2013	VLDB
4	4,625	Stacked Filters: Learning to Filter by Structure	2021	VLDB
5	7,358	Optimizing Collections of Bloom Filters within a Space Budget	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	5,093	Persistent Bloom Filter: Membership Testing for the Entire History	2018	SIGMOD
9	3,703	Stable Learned Bloom Filters for Data Streams	2020	VLDB
10	6,936	A Shifting Bloom Filter Framework for Set Queries	2016	VLDB