Bloomier Filters: A second look

A Bloom filter is a space efficient structure for storing static sets, where the space efficiency is gained at the expense of a small probability of false-positives. A Bloomier filtergeneralizes a Bloom filter to compactly store a function with a static support. In this article we give a simple construction of a Bloomier filter. The construction is linear in space and requires constant time to evaluate. The creation of our Bloomier filter takes linear time which is faster than the existing construction. We show how one can improve the space utilization further at the cost of increasing the time for creating the data structure.

• Publication year

  2008

• Venue

  Embedded Systems and Applications

• Publication date

  2008-07-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-540-87744-8_22arXiv 0807.0928
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Succinct Data Structures for Retrieval and Approximate Membership

  2008cited by this paper
• Hash functions

  2005cited by this paper
• Digital Fountains and Their Application to Informed Content Delivery over Adaptive Overlay Networks

  2005cited by this paper
• Network Applications of Bloom Filters: A Survey

  2004cited by this paper
• The Bloomier filter: an efficient data structure for static support lookup tables

  2004influential reference
• Spectral bloom filters

  2003cited by this paper
• Probabilistic location and routing

  2002cited by this paper
• Self-organization in peer-to-peer systems

  2002cited by this paper
• Informed content delivery across adaptive overlay networks

  2002cited by this paper
• Compressed bloom filters

  2002cited by this paper
• The Difference Between Consecutive Primes, II

  2001cited by this paper
• Summary cache: a scalable wide-area web cache sharing protocol

  2000cited by this paper
• Computing Iceberg Queries E ciently

  1998cited by this paper
• Computing Iceberg Queries Efficiently

  1998cited by this paper
• Dependent Sets of Constant Weight Binary Vectors

  1997cited by this paper
• The Difference Between Consecutive Primes

  1996cited by this paper
• PERF join: an alternative to two-way semijoin and bloomjoin

  1995cited by this paper
• Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems

  1993cited by this paper
• Graphs, Hypergraphs and Hashing

  1993cited by this paper
• Solving Large Sparse Linear Systems over Finite Fields

  1990cited by this paper
• Solving sparse linear equations over finite fields

  1986cited by this paper
• The evolution of random graphs

  1984influential reference
• On the evolution of random graphs

  1984cited by this paper
• Designing a Bloom filter for differential file access

  1982cited by this paper
• Probabilistic algorithm for testing primality

  1980cited by this paper
• Space/time trade-offs in hash coding with allowable errors

  1970cited by this paper
• Approximate formulas for some functions of prime numbers

  1962cited by this paper

• Secure bi-attribute index: Batch membership tests over the non-sensitive attribute

  2025cites this paper
• CodingSketch: A Hierarchical Sketch with Efficient Encoding and Recursive Decoding

  2024cites this paper
• ChainedFilter: Combining Membership Filters by Chain Rule

  2023cites this paper
• Seesaw Counting Filter: An Efficient Guardian for Vulnerable Negative Keys During Dynamic Filtering

  2022influential citation
• Binary Fuse Filters: Fast and Smaller Than Xor Filters

  2022cites this paper
• Chucky: A Succinct Cuckoo Filter for LSM-Tree

  2021cites this paper
• On-device IoT Certificate Revocation Checking with Small Memory and Low Latency

  2021cites this paper
• Concury: a fast and light-weight software cloud load balancer

  2020cites this paper
• PSI from PaXoS: Fast, Malicious Private Set Intersection

  2020cites this paper
• Peeling Close to the Orientability Threshold Spatial Coupling in Hashing-Based Data Structures

  2020cites this paper
• Random hypergraphs for hashing-based data structures

  2020cites this paper
• Don't Work on Individual Data Plane Algorithms. Put Them Together!

  2020cites this paper
• Ludo Hashing

  2020cites this paper
• Concury: A Fast and Light-weighted Software Load Balancer

  2019cites this paper
• Magic Cube Bloom Filter: Answering Membership Queries for Multiple Sets

  2019influential citation
• Xor Filters

  2019cites this paper
• Matrix Bloom Filter: An Efficient Probabilistic Data Structure for 2-tuple Batch Lookup

  2019cites this paper
• Re-designing Compact-structure based Forwarding for Programmable Networks

  2019cites this paper
• Bloom filter variants for multiple sets: a comparative assessment

  2019cites this paper
• Dense Peelable Random Uniform Hypergraphs

  2019cites this paper
• A Model for Learned Bloom Filters and Optimizing by Sandwiching

  2018cites this paper
• Optimizing Bloom Filter: Challenges, Solutions, and Comparisons

  2018cites this paper
• CuCoTrack: Cuckoo Filter Based Connection Tracking

  2018cites this paper
• LOSSY WEIGHT ENCODING FOR DEEP NEURAL NETWORK COMPRESSION

  2018cites this paper
• A resource-frugal probabilistic dictionary and applications in bioinformatics

  2017cites this paper
• EMOMA: Exact Match in One Memory Access

  2017cites this paper
• Weightless: Lossy Weight Encoding For Deep Neural Network Compression

  2017cites this paper
• Difference Bloom Filter: A probabilistic structure for multi-set membership query

  2017cites this paper
• FPGA Implementation of Memory Management for Multigigabit Traffic Monitoring

  2017cites this paper
• BitAV: Fast Anti-Malware by Distributed Blockchain Consensus and Feedforward Scanning

  2016cites this paper
• Monotone Minimal Perfect Hash Functions

  2016cites this paper
• Chitchat: Navigating tradeoffs in device-to-device context sharing

  2016cites this paper
• A Resource-frugal Probabilistic Dictionary and Applications in (Meta)Genomics

  2016cites this paper
• Location privacy without mutual trust: The spatial Bloom filter

  2015cites this paper
• The Grapevine Context Processor: Application Support for Efficient Context Sharing

  2015cites this paper
• Thresholds for Matchings in Random Bipartite Graphs with Applications to Hashing-Based Data Structures

  2015cites this paper
• Ranked Similarity Search of Scientific Datasets: An Information Retrieval Approach

  2014cites this paper
• Spatial Bloom Filters: Enabling Privacy in Location-Aware Applications

  2014cites this paper
• Compressed static functions with applications

  2013influential citation
• Fundamental data structures

  2013cites this paper
• Cache-Oblivious Peeling of Random Hypergraphs

  2013cites this paper
• Various improvements to text fingerprinting

  2013influential citation
• Rethinking Context for Pervasive Computing: Adaptive Shared Perspectives

  2012cites this paper
• Theory and Practice of Bloom Filters for Distributed Systems

  2012cites this paper
• Effiziente Reparatur von Repliken in Distributed Hash Tables

  2012cites this paper
• Grapevine : Efficient Situational Awareness in Pervasive Computing Environments by Evan

  2012cites this paper
• Grapevine: Efficient situational awareness in pervasive computing environments

  2012cites this paper
• Theory and practice of monotone minimal perfect hashing

  2011cites this paper
• Grapevine : Efficient Situational Awareness in Pervasive Computing Environments TR-ARiSE-2011-011

  2011cites this paper
• The Context of Coordinating Groups in Dynamic Mobile Networks

  2011cites this paper
• Fast Prefix Search in Little Space, with Applications

  2010cites this paper
• Conjunctive Filter: Breaking the Entropy Barrier

  2010cites this paper
• Storing a Compressed Function with Constant Time Access

  2009cites this paper
• Theory and Practise of Monotone Minimal Perfect Hashing

  2009cites this paper
• Monotone minimal perfect hashing: searching a sorted table with O(1) accesses

  2009cites this paper
• A Novel Scalable and Storage‐Efficient Architecture for High Speed Exact String Matching

  2009cites this paper
• An Optimal Bloom Filter Replacement Based on Matrix Solving

  2008cites this paper