Skip to content
ZikithezikitPublic

About

Ribbon filters for Python: a static approximate-membership filter that needs fewer bits per key than a Bloom filter. C11 core, no dependencies.

Topics

Resources

Contributing

Security policy

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

pyribbon

pyribbon

PyPI Python versions CI Licence: MIT

Ribbon filters for Python: a static set-membership filter that never misses a key it was built from, and is wrong about any other key with a probability you choose (2**-fp_bits), in fewer bits per key than a Bloom filter. Written in C11 with no Python dependencies. Licensed MIT.

Install

pip install pyribbon

Python 3.10 or newer, from PyPI. Prebuilt wheels cover Linux (x86-64 and ARM, glibc and musl), macOS (Intel and Apple silicon) and Windows (x64), including the free-threaded builds of Python 3.14 and 3.15. On any other platform pip builds the source distribution, and a C compiler is the only build requirement.

Quick start

from pyribbon import RibbonFilter

f = RibbonFilter(["alice", "bob", "carol"], fp_bits=12)  # a wrong "yes" about once in 2**12 lookups
assert "alice" in f  # a member is always found
assert "mallory" not in f  # this non-member was rejected; one in 2**12 would slip through
assert f.contains_many(["alice", "mallory"]) == [True, False]  # one answer per key

Keys can be bytes, str or int. RibbonFilter(keys, width=Width.W128) builds a filter 4% to 8% smaller, in 1.2 to 1.5 times the build time and with slower queries. A filter built from a list, an array.array or a numpy array of integers answers a whole batch with contains_many. Save one with f.to_bytes() and load it back with RibbonFilter.from_buffer(data), which reads the bytes where they are without copying them. Eight runnable scripts in examples/ start with 01_quickstart.py.

Sizes

The false-positive rate is 2**-fp_bits, with fp_bits from 1 to 32 (default 8). Measured at 1,000,000 keys, the 64-byte header included. Bits per key is a decimal because the filter has about 12% more rows than keys, so its size divided by the number of keys is not a whole number. A Bloom filter needs 1.44 * fp_bits bits per key.

fp_bits false-positive rate bits per key
1 50% 1.12
2 25% 2.25
4 6.25% 4.50
6 1.6% 6.75
8 0.39% 8.99
10 0.098% 11.24
12 0.024% 13.49
16 0.0015% 17.99
20 0.000095% 22.48
24 0.0000060% 26.98
28 0.00000037% 31.48
32 0.000000023% 35.97

Performance

Space, build time and lookup time against the number of keys, on one machine (an i7-7700, CPython 3.14, pinned to one core) against pyfusefilter and rbloom. Lower is better in every panel. One machine, one run.

Space per key, build time and lookup time against the number of keys for pyribbon, Fuse8, Xor8 and rbloom

The largest size, against the best other filter of the same fingerprint width:

Where pyribbon wins and loses (int keys, n = 10,000,000):

Class Metric pyribbon Best other Delta Verdict
8-bit bits/key 9.19 9.02 (Fuse8) +2% pyribbon behind
8-bit bits/key above log2(1/FPR) 1.18 1.00 (Fuse8) +17% pyribbon behind
8-bit build ns/key 78 203 (rbloom 2^-8, builtin hash()) -62% pyribbon ahead
8-bit in member ns 91 213 (rbloom 2^-8, builtin hash()) -57% pyribbon ahead
8-bit in non-member ns 94 139 (rbloom 2^-8, builtin hash()) -33% pyribbon ahead
8-bit batch Mkeys/s (50/50 mix) 20.92 5.48 (rbloom 2^-8, builtin hash()) +281% pyribbon ahead
16-bit bits/key 18.39 18.04 (Fuse16) +2% pyribbon behind
16-bit bits/key above log2(1/FPR) 2.36 1.95 (Fuse16) +21% pyribbon behind
16-bit build ns/key 93 423 (rbloom 2^-16, builtin hash()) -78% pyribbon ahead
16-bit in member ns 131 411 (rbloom 2^-16, builtin hash()) -68% pyribbon ahead
16-bit in non-member ns 109 162 (rbloom 2^-16, builtin hash()) -33% pyribbon ahead
16-bit batch Mkeys/s (50/50 mix) 12.24 3.40 (rbloom 2^-16, builtin hash()) +260% pyribbon ahead

Delta is relative to the best other filter of the same fingerprint class, including rbloom with its builtin hash(); a negative delta means pyribbon is lower. Lower is better except for batch throughput. The 'above log2(1/FPR)' rows move with the measured FPR, whose uncertainty is in the notes. The batch row compares contains_many with the other libraries' per-key loop, because none of them has a batch API. The table is computed from the raw results of this run.

More

Everything else is in docs/: the usage guide, the API reference, the limits, how it works, the internals (hashing, the file format, the C core) and the full performance numbers by number of keys. The C core builds and tests on its own: see core/README.md. To work on pyribbon, read CONTRIBUTING.md. To report a vulnerability, read SECURITY.md.

Licence and credits

pyribbon is MIT licensed (LICENSE). The vendored xxHash header (core/vendor/xxhash.h) is BSD 2-Clause (LICENSES/). The algorithm is by Peter C. Dillinger and Stefan Walzer, in "Ribbon filter: practically smaller than Bloom and Xor" (arXiv:2103.02515). This implementation was written from their papers, not from existing code.

About

Ribbon filters for Python: a static approximate-membership filter that needs fewer bits per key than a Bloom filter. C11 core, no dependencies.

Topics

Resources

Contributing

Security policy

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages