inbloom

README

inbloom

A fast bloom filter written in Go.

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set.

https://en.wikipedia.org/wiki/Bloom_filter

Usage

package main

import (
	"bytes"
	"fmt"

	"github.com/rhinof/inbloom"
)

func main() {

	//Probability of false positives
	fpRate := 0.1
	// Estimated set size
	expectedSetSize := int64(100000)
	data := bytes.NewBufferString("rhinof").Bytes()

	//Create the filter
	filter := inbloom.NewFilter(fpRate, expectedSetSize)

	if err := filter.Add(&data); err != nil {
		fmt.Print("couldn't add element")
	}

	result, _ := filter.Test(&data)

	fmt.Printf("test returned %t", result)
}

Documentation

Index

• type BloomFilter
  • func (filter *BloomFilter) Add(obj *[]byte) error
  • func (filter *BloomFilter) FillRatio() float64
  • func (filter *BloomFilter) PoFP() float64
  • func (filter BloomFilter) Test(obj *[]byte) (bool, error)
• type ProbabilisticSet
  • func NewFilter(p float64, n int) (filter ProbabilisticSet, e error)

Types

type BloomFilter

type BloomFilter struct {
	// contains filtered or unexported fields
}

BloomFilter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set.

func (*BloomFilter) Add

func (filter *BloomFilter) Add(obj *[]byte) error

Add an object to the set

func (*BloomFilter) FillRatio

func (filter *BloomFilter) FillRatio() float64

FillRatio returns

func (*BloomFilter) PoFP

func (filter *BloomFilter) PoFP() float64

PoFP returns the probobility of false positives given the saturation of the filter

func (BloomFilter) Test

func (filter BloomFilter) Test(obj *[]byte) (bool, error)

Test if an element is in the set

type ProbabilisticSet

type ProbabilisticSet interface {
	Add(obj *[]byte) error

	PoFP() float64
	Test(obj *[]byte) (bool, error)
}

ProbabilisticSet represents an abstraction of a Probabilistic

func NewFilter

func NewFilter(p float64, n int) (filter ProbabilisticSet, e error)

NewFilter creates a new BloomFilter. p is the error rate and n is the estimated number of elements that will be handled by the filter