[ bsd3, data, library ] [ Propose Tags ]

Versions

0.1.0.0, 0.1.0.1, 0.1.0.2, 0.1.0.3 (info)

Change log

CHANGELOG.md

Dependencies

arithmoi (>=0.3 && <0.5), base (>=4.7 && <4.10), binary (>=0.7 && <0.9), bytestring (>=0.9 && <0.11), hashable (==1.2.*), hedis (>=0.5 && <0.10) [details]

License

BSD-3-Clause

Copyright

Copyright 2016 Tobias Markus

Author

Tobias Markus

Maintainer

Tobias Markus

Category

Data

Source repo

head: git clone https://github.com/hesiod/bloomfilter-redis.git

Uploaded

by hesiod at Sat Jun 4 15:58:42 UTC 2016

Distributions

NixOS:0.1.0.3

Downloads

890 total (19 in the last 30 days)

Rating

2.0 (votes: 1) [estimated by rule of succession]

Your Rating

  • λ

  • λ

  • λ

Status

Docs available [build log]
Last success reported on 2016-06-04 [all 1 reports]
Hackage Matrix CI

Distributed bloom filters on Redis (using the Hedis client).

The hash family algorithm is partly inspired by Brian O’Sullivan’s bloomfilter package at https://hackage.haskell.org/package/bloomfilter.

[Skip to Readme]

Modules

[Index]

Downloads

Maintainer’s Corner

For package maintainers and hackage trustees

Readme for bloomfilter-redis-0.1.0.3

[back to package description]

bloomfilter-redis Build Status

Distributed bloom filters on Redis (using the Hedis client).

The hash family algorithm is partly inspired by Brian O’Sullivan’s bloomfilter package.

Features

  • Implementation of the FNV-1/FNV-1a hash function is included

  • Automatic derivation of a hash family from a single hash function as described by Kirsch and Mitzenmacher

  • The bloom filter is distributed without extra effort since Redis does the heavy lifting

  • Every Hashable type can be added to the bloom filter

  • Every Binary type can be hashed

Benchmark and Testing suite

A benchmark for the FNV hash function is included and can be invoked using cabal bench or stack bench. An HTML report is generated as report.html.

A testing suite using tasty is included.

Further Information

Todo

  • Separate the FNV hash function into a separate package

  • The actual operations (addBF, queryBF, etc) should ideally live in a MonadReader (Bloom a), but this requires some work on the Hedis side because of RedisCtx

Caveats

  • The only supported FNV hash sizes are 32 and 64 bits. Support for larger widths is a matter of having a data type with instances for FiniteBitsand Num.

  • The offset basis (fnvOffsetBasis) is not correctly computed, although this has absolutely no effect on the performance of the hash function in practice.