We study the problem of constructing a dynamic fully indexable dictionary (FID) in the Word-RAM model using space close to the information-theoretic lower bound. A FID is a data-structure that encodes a bit-vector B of length u and answers, for b∈{0,1}, rankb(B, x)=|{y≤ x | B[y]=b}| and selectb(B, r)=min{0≤ x

We present the first parallel architecture for a dynamic approximate membership data-structure (i.e., a filter) that supports insertions, deletions, and approximate membership queries. Our architecture borrows techniques from PRAM emulation to obtain a parallel filter based on two levels of fingerprint-dictionaries. A key component in the architecture is a special-purpose wide-word processor we designed to support operations over small dictionaries. We implemented this architecture on an FPGA running at 100MHz. The implementation stores up to 1.44 million keys, has a false-positive rate less than 0.3%, receives batches 16 of operations per cycle, preserves sequential order, and runs with a stable throughput of over a billion operations per second with respect to several benchmarks.