A bloom filter is a probabilistic data structure that is used to determine if an element is present in a set

Overview

gobloomgo

A bloom filter is a probabilistic data structure that is used to determine if an element is present in a set.

Bloomdb implements a bloom filter in Go, while using boltdb and badgerdb as optional in-memory persistent storage.

Bloomdb also implement a scalable bloom filter described in a paper written by P. Almeida, C.Baquero, N. Preguiça, D. Hutchison.

A scalable bloom filter allows you to grow the filter as needed, and removes the need for an apriori filter size as expected by the basic bloom filter, while preserving the desired false positive rate by scaling the filter as needed.

Installation

go get github.com/dsa0x/gobloomgo

Usage

gobloomgo contains implementation of both the normal and scalable bloom filter via the methods below:

bf := gobloomgo.NewBloom(0.01, 100, nil)
sbf := gobloomgo.NewScalableBloom(0.9, 100, nil)

With a persistent store

gobloomgo supports boltdb and badgerdb as persistent store. Using them is very simple. gobloomgo exposes methods that initializes the database and then they can be attached to the bloom filter

Using Boltdb
// initialize boltdb
db := gobloomgo.NewBolt("/tmp/test.db", 0600)

// you can also setup options supported by bolt to configure your store
opts := bbolt.Options{
		Timeout: 10 * time.Second,
	}
db = gobloomgo.NewBolt("/tmp/test.db", 0600, opts)
defer db.Close()

bf := gobloomgo.NewBloom(0.01, 100, db)
Badgerdb (v3)
// initialize badgerdb
db := gobloomgo.NewBadger()

// initialize badgerdb with options
opts := badger.DefaultOptions("/tmp/bloom.db")
db = gobloomgo.NewBadger(opts)

bf := gobloomgo.NewBloom(0.01, 100, db)

Using Scalable bloom filter

// initialize badgerdb
db := gobloomgo.NewBadger()

sbf := gobloomgo.NewScalableBloom(0.9, 100, db)

Example

package main

import (
	"fmt"

	"github.com/dgraph-io/badger/v3"
	"github.com/dsa0x/gobloomgo"
)

func main() {

	bf := gobloomgo.NewScalableBloom(0.01, 100, nil)
	bf.Find([]byte("foo"))

	// with a persistent store
	opts := badger.DefaultOptions("/tmp/bloom.db")
	db := gobloomgo.NewBadger(opts)
	bf := gobloomgo.NewScalableBloom(0.9, 100, db)

	bf.Add([]byte("key"), []byte("bar"))
	fmt.Printf("%s\n", bf.Get([]byte("key")))
}

References

  1. P. Almeida, C.Baquero, N. Preguiça, D. Hutchison
Releases(v0.0.3)
Owner
Samsondeen
Samsondeen
go/golang: fast bit set Bloom filter

package implements a fast bloom filter with real 'bitset' and JSONMarshal/JSONUnmarshal to store/reload the Bloom filter.

Andreas Briese 121 Aug 2, 2022
A Go implementation of an in-memory bloom filter, with support for boltdb and badgerdb as optional data persistent storage.

Sprout A bloom filter is a probabilistic data structure that is used to determine if an element is present in a set. Bloom filters are fast and space

Samsondeen 26 Jul 4, 2022
Cuckoo Filter: Practically Better Than Bloom

Cuckoo Filter Cuckoo filter is a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient

Seif Lotfy 917 Aug 1, 2022
Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

Tanner Ryan 126 May 10, 2022
A simple Bloom Filter implementation in Go

This is a simple Bloom filter implementation written in Go. For the theory behind Bloom filters, read http://en.wikipedia.org/wiki/Bloom_filter This

Damian Gryski 16 Apr 26, 2018
Leaked password check library with bloom filter

Leaked password check With this library you can check the password is probably leaked or not. Pre generated bitset DB includes 6 Million leaked passwo

Kaan Karakaya 41 Dec 2, 2021
Probabilistic data structures for processing continuous, unbounded streams.

Boom Filters Boom Filters are probabilistic data structures for processing continuous, unbounded streams. This includes Stable Bloom Filters, Scalable

Tyler Treat 1.5k Aug 1, 2022
A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Studio Sol Comunicação Digital Ltda 21 Jul 22, 2022
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Fatih Arslan 650 Jul 19, 2022
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Fatih Arslan 651 Aug 2, 2022
Disjoint Set data structure implementation in Go

dsu Implementation of the Disjoint-Set data structure. The Disjoint-Set, Also called a Union-Find or Merge-Find set, is a data structure that stores a

Iheb Haboubi 6 Jan 29, 2022
Recursively searches a map[string]interface{} structure for another map[string]interface{} structure

msirecurse Recursively searches a map[string]interface{} structure for existence of a map[string]interface{} structure Motivation I wrote this package

Fred Moyer 1 Mar 3, 2022
Go package implementing Bloom filters

Bloom filters A Bloom filter is a representation of a set of n items, where the main requirement is to make membership queries; i.e., whether an item

Will Fitzgerald 1.6k Aug 6, 2022
Go package implementing Bloom filters

Bloom filters A Bloom filter is a concise/compressed representation of a set, where the main requirement is to make membership queries; i.e., whether

Go language BitSet and Bloom filter 1.6k Aug 1, 2022
Sync distributed sets using bloom filters

goSetReconciliation An implementation to sync distributed sets using bloom filters. Based on the paper "Low complexity set reconciliation using Bloom

Elton SV 25 Jan 4, 2022
Bitset data structure

Your basic bit Set data structure for positive numbers A bit array, or bit set, is an efficient set data structure. It consists of an array that compa

Algorithms to Go 127 Jul 29, 2022
Data structure and algorithm library for go, designed to provide functions similar to C++ STL

GoSTL English | 简体中文 Introduction GoSTL is a data structure and algorithm library for go, designed to provide functions similar to C++ STL, but more p

stirlingx 692 Aug 8, 2022
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

Derek Parker 597 Jul 31, 2022
BTree provides a simple, ordered, in-memory data structure for Go programs.

BTree implementation for Go This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure. The API is

Google 2.9k Aug 10, 2022