andrewdalpino / okbloomer
An autoscaling Bloom filter with ultra-low memory usage for PHP.
Fund package maintenance!
andrewdalpino
Installs: 386 493
Dependents: 2
Suggesters: 0
Security: 0
Stars: 3
Watchers: 2
Forks: 1
Open Issues: 2
Requires
- php: >=7.4
Requires (Dev)
- friendsofphp/php-cs-fixer: ^3.0
- phpbench/phpbench: ^1.0
- phpstan/extension-installer: ^1.0
- phpstan/phpstan: ^1.0
- phpstan/phpstan-phpunit: ^1.0
- phpunit/phpunit: ^9.5
This package is auto-updated.
Last update: 2024-11-05 05:34:19 UTC
README
An autoscaling Bloom filter with ultra-low memory footprint for PHP. Ok Bloomer employs a novel layered filtering strategy that allows it to expand while maintaining an upper bound on the false positive rate. Each layer is comprised of a bitmap that remembers the hash signatures of the items inserted so far. If an item gets caught in the filter, then it has probably been seen before. However, if an item passes through the filter, then it definitely has never been seen before.
- Ultra-low memory footprint
- Autoscaling works on streaming data
- Bounded maximum false positive rate
- Open-source and free to use commercially
Installation
Install into your project using Composer:
$ composer require andrewdalpino/okbloomer
Requirements
- PHP 7.4 or above
Bloom Filter
A probabilistic data structure that estimates the prior occurrence of a given item with a maximum false positive rate.
Parameters
Example
use OkBloomer\BloomFilter; $filter = new BloomFilter(0.01, 4, 32000000); $filter->insert('foo'); echo $filter->exists('foo'); echo $filter->existsOrInsert('bar'); echo $filter->exists('bar');
true
false
true
Testing
To run the unit tests:
$ composer test
Static Analysis
To run static code analysis:
$ composer analyze
Benchmarks
To run the benchmarks:
$ composer benchmark
References
- [1] P. S. Almeida et al. (2007). Scalable Bloom Filters.