eXpress “1.5”
|
The RobertsFilter class implements a datastructure to test for repeats of a key with high probability, when repeats are most likely to be nearby. More...
#include <robertsfilter.h>
Public Member Functions | |
RobertsFilter (size_t local_size=DEFAULT_LOC_SIZE, size_t global_size=DEFAULT_GLOB_SIZE) | |
RobertsFilter constructor sets the size of the sets. | |
bool | test_and_push (const std::string &key) |
A member function that tests for membership of the key in either set. |
The RobertsFilter class implements a datastructure to test for repeats of a key with high probability, when repeats are most likely to be nearby.
Recently observed keys are stored in a local set for a certain number of observations (set by local_size). After this number of observations, it is removed from the local set, and placed in the global set, displacing a random element of this set. To be used when the full set cannot be stored in memory.
Definition at line 30 of file robertsfilter.h.
RobertsFilter::RobertsFilter | ( | size_t | local_size = DEFAULT_LOC_SIZE , |
size_t | global_size = DEFAULT_GLOB_SIZE |
||
) |
RobertsFilter constructor sets the size of the sets.
local_size | the maximum number of keys to store in the local set. |
global_size | the maximum number of keys to store in the global set. |
Definition at line 13 of file robertsfilter.cpp.
bool RobertsFilter::test_and_push | ( | const std::string & | key | ) |
A member function that tests for membership of the key in either set.
If not found, the key is added to the local set, possibly pushing the oldest key in the local set into the global set, which may displace a global key.
key | the key to be tested for and pushed into the local set. |
Definition at line 19 of file robertsfilter.cpp.