Skip to content

Latest commit

 

History

History
39 lines (31 loc) · 1.33 KB

README.md

File metadata and controls

39 lines (31 loc) · 1.33 KB
Raw

Cuculiform

Cuculiform is a simple Cuckoo filter implementation as C++11 single-header library, independent from the reference implementation.

A Cuckoo filter is a space-efficient probabilistic data structure for fast set membership testing. They have properties similar to Bloom filters, but in contrast, Cuckoo filters support deletion.

For details about the algorithm, see: "Cuckoo Filter: Practically Better Than Bloom" in proceedings of ACM CoNEXT 2014 by Bin Fan, Dave Andersen and Michael Kaminsky

Build Instructions

Cuculiform depends on HighwayHash being present for its default hash function, but the hash function is interchangeable.

git clone https://git.scc.kit.edu/dsn-projects/nsm/cuculiform.git
git clone https://github.com/google/highwayhash.git
git clone https://github.com/google/cityhash.git

cd highwayhash
make -j$(nproc)

cd ../cityhash
./configure --prefix="$(pwd)" --with-pic
make all check CXXFLAGS="-g -O3"
make install

cd ../cuculiform
mkdir build
cd build
cmake ..
make
./cuculiform_test

Name Origin

cuculiform, def.: cuckoo-like, part of the order Cuculiformes