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: 3498
Venue: SIGMOD
Year: 2003
Pagerank: 0.00013532857
Overall Rank: 862 | 94.09%
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,975	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	9.3645236e-05
2,043	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	9.2674387e-05
3,510	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.3561488e-05
3,533	Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters	2006	SIGMOD	7.3366144e-05
4,073	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.9242783e-05
4,683	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB	6.5641059e-05
4,691	Fast Processing and Querying of 170TB of Genomics Data via a Repeated And Merged BloOm Filter (RAMBO)	2021	SIGMOD	6.5609196e-05
4,863	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.4740702e-05
4,971	Persistent Bloom Filter: Membership Testing for the Entire History	2018	SIGMOD	6.4195676e-05
5,459	Bloom Histogram: Path Selectivity Estimation for XML Data with Updates	2004	VLDB	6.2108888e-05
6,060	Finding Global Icebergs over Distributed Data Sets	2006	PODS	5.9914746e-05
8,020	Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams	2013	VLDB	5.5059287e-05
8,356	Optimistic Data Parallelism for FPGA-Accelerated Sketching	2023	VLDB	5.4450094e-05
8,408	A Shifting Bloom Filter Framework for Set Queries	2016	VLDB	5.4312165e-05
8,612	Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying	2021	SIGMOD	5.4012878e-05
9,084	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS	5.3251649e-05
9,329	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.2894515e-05
9,497	Rank Join Queries in NoSQL Databases	2014	VLDB	5.2608378e-05
9,718	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.2323504e-05
10,004	A four-dimensional Analysis of Partitioned Approximate Filters	2021	VLDB	5.1810297e-05
10,238	Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor	2026	SIGMOD	5.093636e-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.00052982574
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
342	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00020673706
577	Computing Iceberg Queries Efficiently	1998	VLDB	0.00016235949
730	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014539362
1,186	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011764128

Semantically Similar Papers

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