Prefix Filter: Practically and Theoretically Better Than Bloom

Tomer Even, Guy Even, Adam Morrison

Many applications of approximate membership query data structures, or filters, require only an incremental filter that supports insertions but not deletions. However, the design sp…