quotient_filter_example.C File Reference

Quotient filter in Aleph-w: probabilistic set with deletion support. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <tclap/CmdLine.h>
#include <quotient-filter.H>

Include dependency graph for quotient_filter_example.C:

Go to the source code of this file.

Functions
void	print_section (const string &title)
void	print_sub (const string &title)
void	demo_basic ()
void	demo_fp ()
void	demo_comparison ()
void	demo_merge ()
void	demo_cache ()
int	main (int argc, char *argv[])

Detailed Description

Quotient filter in Aleph-w: probabilistic set with deletion support.

Overview

Demonstrates Quotient_Filter<T>: a cache-friendly probabilistic set that supports insertion, membership testing, and deletion — unlike Bloom filters.

Sections:

• basic: insert / query / delete
• fp: false positive rate analysis
• vs: comparison with Bloom filter
• merge: merging two filters
• cache: practical cache-filter application

Usage

./quotient_filter_example                 # run all
./quotient_filter_example -s basic        # run one section
./quotient_filter_example --help

Author

Leandro Rabindranath León

Definition in file quotient_filter_example.C.

Function Documentation

demo_basic()

void demo_basic

(

)

Definition at line 59 of file quotient_filter_example.C.

References Aleph::divide_and_conquer_partition_dp(), print_section(), print_sub(), tests(), and w.

Referenced by main().

demo_cache()

void demo_cache

(

)

Definition at line 223 of file quotient_filter_example.C.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::from_capacity(), and print_section().

Referenced by main().

demo_comparison()

void demo_comparison

(

)

Definition at line 155 of file quotient_filter_example.C.

References Aleph::divide_and_conquer_partition_dp(), and print_section().

Referenced by main().

demo_fp()

void demo_fp

(

)

Definition at line 116 of file quotient_filter_example.C.

References Aleph::divide_and_conquer_partition_dp(), and print_section().

Referenced by main().

demo_merge()

void demo_merge

(

)

Definition at line 190 of file quotient_filter_example.C.

References Aleph::Quotient_Filter< T >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::insert(), Aleph::Quotient_Filter< T >::merge(), print_section(), seed, and Aleph::Quotient_Filter< T >::size().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 279 of file quotient_filter_example.C.

References cmd, demo_basic(), demo_cache(), demo_comparison(), demo_fp(), demo_merge(), Aleph::divide_and_conquer_partition_dp(), and section().

print_section()

void print_section

(

const string &

title

)

Definition at line 43 of file quotient_filter_example.C.

Referenced by demo_basic(), demo_cache(), demo_comparison(), demo_fp(), and demo_merge().

print_sub()

void print_sub

(

const string &

title

)

Definition at line 50 of file quotient_filter_example.C.

Referenced by demo_basic().