dlcbf

README

dlCBF

A d-left Counting Bloom Filter (dlCBF) is simple hashing-based Counting Bloom Filter (CBF) alternative based on d-left hashing that offers the same functionality as a CBF, but uses less space, generally saving a factor of two or more.

For details about the algorithm and citations please use this article for now

"Bloom Filters via d-Left Hashing and Dynamic Bit Reassignment Extended Abstract" by Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh and George Varghese

Note:

• This implmentation currently does not implement the counter feature. (coming soon)
• Insertions of items that already exists in the filter will fail (item can only exist once).
• fingerprint size set to a static 16 Bit (also to be changed soon)

Usage

dlcbf, err := NewDlcbfForCapacity(1000000)
	
// Add Item
dlcbf.Add("jon snow is alive")

count := dlcbf.GetCount() // count >> 1

member := dlcbf.IsMember("jon snow is alive") // member = true
	
// Remove Item
dlcbf.Delete("jon snow is alive") // returns true

// Remove Item again
dlcbf.Delete("jon snow is alive") // returns false
	
count := dlcbf.GetCount() // count >> 0

Documentation

Index

• type Dlcbf
  • func NewDlcbf(numTables uint, numBuckets uint) (*Dlcbf, error)
  • func NewDlcbfForCapacity(capacity uint) (*Dlcbf, error)
  • func (dlcbf *Dlcbf) Add(data []byte) bool
  • func (dlcbf *Dlcbf) AddBatch(datas [][]byte) []bool
  • func (dlcbf *Dlcbf) ClearAll()
  • func (dlcbf *Dlcbf) Count() uint
  • func (dlcbf *Dlcbf) Decode(bytes []byte) error
  • func (dlcbf *Dlcbf) Delete(data []byte) bool
  • func (dlcbf *Dlcbf) DeleteBatch(datas [][]byte) []bool
  • func (dlcbf *Dlcbf) Encode() ([]byte, error)
  • func (dlcbf *Dlcbf) Get(data []byte) uint8
  • func (dlcbf *Dlcbf) GetBatch(datas [][]byte) []uint8
  • func (dlcbf *Dlcbf) ReadFrom(stream io.Reader) (int64, error)
  • func (dlcbf *Dlcbf) TestAddBatch(datas [][]byte) []bool
  • func (dlcbf *Dlcbf) TestAndAdd(data []byte) bool
  • func (dlcbf *Dlcbf) WriteTo(stream io.Writer) (int64, error)

Types

type Dlcbf

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

Dlcbf is a struct representing a d-left Counting Bloom Filter

func NewDlcbf

func NewDlcbf(numTables uint, numBuckets uint) (*Dlcbf, error)

NewDlcbf returns a newly created Dlcbf

func NewDlcbfForCapacity

func NewDlcbfForCapacity(capacity uint) (*Dlcbf, error)

NewDlcbfForCapacity returns a newly created Dlcbf for a given max Capacity

func (*Dlcbf) Add

func (dlcbf *Dlcbf) Add(data []byte) bool

func (*Dlcbf) AddBatch

func (dlcbf *Dlcbf) AddBatch(datas [][]byte) []bool

func (*Dlcbf) ClearAll

func (dlcbf *Dlcbf) ClearAll()

func (*Dlcbf) Count

func (dlcbf *Dlcbf) Count() uint

GetCount returns cardinlaity count of current filter

func (*Dlcbf) Decode

func (dlcbf *Dlcbf) Decode(bytes []byte) error

func (*Dlcbf) Delete

func (dlcbf *Dlcbf) Delete(data []byte) bool

func (*Dlcbf) DeleteBatch

func (dlcbf *Dlcbf) DeleteBatch(datas [][]byte) []bool

func (*Dlcbf) Encode

func (dlcbf *Dlcbf) Encode() ([]byte, error)

func (*Dlcbf) Get

func (dlcbf *Dlcbf) Get(data []byte) uint8

func (*Dlcbf) GetBatch

func (dlcbf *Dlcbf) GetBatch(datas [][]byte) []uint8

func (*Dlcbf) ReadFrom

func (dlcbf *Dlcbf) ReadFrom(stream io.Reader) (int64, error)

func (*Dlcbf) TestAddBatch

func (dlcbf *Dlcbf) TestAddBatch(datas [][]byte) []bool

func (*Dlcbf) TestAndAdd

func (dlcbf *Dlcbf) TestAndAdd(data []byte) bool

func (*Dlcbf) WriteTo

func (dlcbf *Dlcbf) WriteTo(stream io.Writer) (int64, error)