BF-Trie: an index for Bloom filters, to find Bloom filters including in or included by a given Bloom filter.
cmake ${opt} .
make
opt:
- -Duse_atree=ON: testing A-Tree
- -Duse_trie=ON: testing Trie tree
- -Duse_list=ON: testing Arraylist
- -Dinverse=ON: testing the index for V-method
- -Dinverse=OFF: testing the index for V-method (by default)
- -Dbloom_table_size=8: the bloom filter bitmap size (int bytes) (as 8 by default)
- -Dbloom_table_size=16: the number of hash functions (as 16 by default)
./Trie ${sr} ${ir} ${t} ${n} ${range}
- ${sr}: ratio of S-type bloom filters
- ${ir}: ratio of insert operations
- ${t}: number of threads
- ${n}: number of preloaded bloom filter
- ${range}: number of elements inserted into S-type bloom filters (optimal, 10 by default)
- BloomFilterTest/: calculate the false positive rate of normal Bloom filters and prefix Bloom filters based on simulation.
- analysis projects/: the codes of projects that were done the code survey.
To use the index for cache invalidation, you should include the libbftree.a in your code, and we provide a set of APIs:
- CreateIndex(): create an empty index;
- IndexInsert(index, meta): insert a signature
meta
into the index. Specifically, eachmeta
holds a Bloom filter which should be generated for a DB query. For the D-method, themeta
is generated for a DQL query and thequeryId
attribute of themeta
should also be filled to identify the related cached entry during Search. For V-method, ameta
is generated for each updated tuple. Specifically, to insert an identifier into a Bloom filter, you can also include this lib and use the APIBloomInsertKey
, which implements the prefix hashing. - IndexSearch(index, meta,list): lookup based on the give
meta
. For the D-method, the found matched cases are stored in list; for V-method, it returnstrue
if any matched case is found, i.e., the checked cached entry should be invalidated.