member: implement vBF mode
authorYipeng Wang <yipeng1.wang@intel.com>
Wed, 4 Oct 2017 03:12:21 +0000 (20:12 -0700)
committerThomas Monjalon <thomas@monjalon.net>
Sun, 8 Oct 2017 22:02:45 +0000 (00:02 +0200)
commit54b8edc07c5572c97124efb4227aff52b66b9a5f
treef51a4e8e536cd61e5deb7d98a4c52f279fc9c789
parent904ec78a239c249ff5fb688809d9a64e8242814e
member: implement vBF mode

Bloom Filter (BF) [1] is a well-known space-efficient
probabilistic data structure that answers set membership queries.
Vector of Bloom Filters (vBF) is an extension to traditional BF
that supports multi-set membership testing. Traditional BF will
return found or not-found for each key. vBF will also return
which set the key belongs to if it is found.

Since each set requires a BF, vBF should be used when set count
is small. vBF's false positive rate could be set appropriately so
that its memory requirement and lookup speed is better in certain
cases comparing to HT based set-summary.

This patch adds the vBF implementation.

[1]B H Bloom, “Space/Time Trade-offs in Hash Coding with Allowable
Errors,” Communications of the ACM, 1970.

Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
Reviewed-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
lib/librte_member/Makefile
lib/librte_member/rte_member.c
lib/librte_member/rte_member.h
lib/librte_member/rte_member_vbf.c [new file with mode: 0644]
lib/librte_member/rte_member_vbf.h [new file with mode: 0644]