Bloom filter available?

Is there any package containing a bloom filter ?
Optimum would be a bloom-filter, directly usuable from LUA.

  • Filtering what?
  • Why would you seek a filter that only produces a possible answer?

Are you merely seeking code?

There are quite a few apps, where bloom filters are to be used, i.e. in caching. Just asking for a package, (also) containing bloom filter, or similar. I.e. redis for full LINUX has this option, but not on openwrt.
Looks like I will need to offer some "incentive" :slight_smile:

You plan to work with data sets so large that a regular hash map would be space inefficient, .... on a router?

Lua has hash maps built in by default. (in fact, it doesn't do arrays, arrays are just hash maps that use integers as the keys). You could create k hash functions by implementing one hash function and a set of "keys", so you're hashing:

my_hash(key[i] .. mystring)

create a lua array with indexes 1...N where N is a prime integer sufficiently large for your purpose.

Then insert basically means calculate each hash and take it modulo N, and set the value of the array cell to 1.

query basically means calculate all the hashes and check if all the cells are 1.

If you read the "keys" from /dev/urandom it should be good enough.

This seems like about 30 lines of Lua code.

Yes. Although an openwrt device is not always only a router.

1 Like

Let us know if you build it and it works well for you.