bloomfilter-redis: Distributed bloom filters on Redis (using the Hedis client).

[ bsd3, data, library ] [ Propose Tags ]

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]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0, 0.1.0.1, 0.1.0.2, 0.1.0.3, 0.1.0.4 (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 && <1.3), hedis (>=0.5 && <0.9) [details]
License BSD-3-Clause
Copyright Copyright 2016 Tobias Markus <tobias AT miglix DOT eu>
Author Tobias Markus <tobias AT miglix DOT eu>
Maintainer Tobias Markus <tobias AT miglix DOT eu>
Category Data
Source repo head: git clone https://github.com/hesiod/bloomfilter-redis.git
Uploaded by hesiod at 2016-04-17T17:41:16Z
Distributions
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 3193 total (8 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2016-04-17 [all 1 reports]

Readme for bloomfilter-redis-0.1.0.2

[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 FiniteBits and Num.
  • The offset basis (fnvOffsetBasis) is not correctly computed, although this has absolutely no effect on the performance of the hash function in practice.