eXpress “1.5”

RobertsFilter Class Reference

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>

List of all members.

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.

Detailed Description

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.

Author:
Adam Roberts
Date:
2011 Artistic License 2.0

Definition at line 30 of file robertsfilter.h.


Constructor & Destructor Documentation

RobertsFilter::RobertsFilter ( size_t  local_size = DEFAULT_LOC_SIZE,
size_t  global_size = DEFAULT_GLOB_SIZE 
)

RobertsFilter constructor sets the size of the sets.

Parameters:
local_sizethe maximum number of keys to store in the local set.
global_sizethe maximum number of keys to store in the global set.

Definition at line 13 of file robertsfilter.cpp.


Member Function Documentation

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.

Parameters:
keythe key to be tested for and pushed into the local set.
Returns:
True iff the key is in the local or global set.

Definition at line 19 of file robertsfilter.cpp.


The documentation for this class was generated from the following files:
 All Classes Functions Variables