DBScholar

Back to papers

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.00013338
Overall Rank
872 | 94.15%
DOI
10.1145/872757.872787

Incoming Non-self Citations Over Time

Authors

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,846 Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity 2018 VLDB 9.511501e-05
2,073 A General-Purpose Counting Filter: Making Every Bit Count 2017 SIGMOD 9.0833741e-05
3,285 Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput 2019 VLDB 7.4525495e-05
3,547 Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters 2006 SIGMOD 7.2088273e-05
3,701 Stable Learned Bloom Filters for Data Streams 2020 VLDB 7.0820503e-05
4,735 Fast Processing and Querying of 170TB of Genomics Data via a Repeated And Merged BloOm Filter (RAMBO) 2021 SIGMOD 6.4423242e-05
4,782 False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams 2004 VLDB 6.4144338e-05
4,981 Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams 2017 VLDB 6.3271e-05
5,096 Persistent Bloom Filter: Membership Testing for the Entire History 2018 SIGMOD 6.2747628e-05
5,581 Bloom Histogram: Path Selectivity Estimation for XML Data with Updates 2004 VLDB 6.0741907e-05
6,191 Finding Global Icebergs over Distributed Data Sets 2006 PODS 5.8543576e-05
6,938 A Shifting Bloom Filter Framework for Set Queries 2016 VLDB 5.6373445e-05
7,186 Building Fast and Compact Sketches for Approximately Multi-Set Multi-Membership Querying 2021 SIGMOD 5.5886598e-05
8,145 Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams 2013 VLDB 5.3897281e-05
8,522 Optimistic Data Parallelism for FPGA-Accelerated Sketching 2023 VLDB 5.3225121e-05
9,268 Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform 2013 PODS 5.2032182e-05
9,520 Panakos: Chasing the Tails for Multidimensional Data Streams 2023 VLDB 5.1683226e-05
9,688 Rank Join Queries in NoSQL Databases 2014 VLDB 5.1403642e-05
9,897 Sharing Aggregate Computation for Distributed Queries 2007 SIGMOD 5.1125291e-05
10,146 A four-dimensional Analysis of Partitioned Approximate Filters 2021 VLDB 5.071058e-05
10,464 Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor 2026 SIGMOD 4.9769913e-05
Previous Page 1 / 1 Next

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.00052097907
124 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00030586757
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028621958
345 R* Optimizer Validation and Performance Evaluation for Distributed Queries 1986 VLDB 0.0002045459
588 Computing Iceberg Queries Efficiently 1998 VLDB 0.00015899635
746 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014282427
1,203 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011543634
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 11,887 New Wine in an Old Bottle: Data-Aware Hash Functions for Bloom Filters 2022 VLDB
2 10,146 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,627 Stacked Filters: Learning to Filter by Structure 2021 VLDB
5 7,362 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,195 Prefix Filter: Practically and Theoretically Better Than Bloom 2022 VLDB
8 5,096 Persistent Bloom Filter: Membership Testing for the Entire History 2018 SIGMOD
9 3,701 Stable Learned Bloom Filters for Data Streams 2020 VLDB
10 6,938 A Shifting Bloom Filter Framework for Set Queries 2016 VLDB