README
¶
Age-Partitioned Bloom Filters
Age-Partitioned Bloom Filters (APBF) is a novel approach for duplicate detection in sliding windows over an unbounded stream of items described in Age-Partitioned Bloom Filters: Ariel Shtul, Carlos Baquero and Paulo Sérgio Almeida, 2020.
The implementation employs the enhanced double hashing technique for fast index computation introduced in Bloom Filters in Probabilistic Verification: Peter C. Dillinger and Panagiotis Manolios, 2004.
Example
// create a filter with k=10, l=7, and g=1000
filter := apbf.New(10, 7, 1000)
item := []byte("test item")
filter.Add(item)
if filter.Query(item) {
fmt.Println("item was found")
}
Installation
Use go get to add the project to your workspace:
go get -u github.com/CrowdStrike/apbf
Benchmarks
The following results show the performance of main filter operations Add and Query with and without refresh enabled for a small and large filter. Benchmarks were executed on a MacBook Pro 2017 dev laptop.
BenchmarkSmallFilterAdd-8 20000000 103 ns/op 0 B/op 0 allocs/op
BenchmarkSmallFilterAddWithRefresh-8 10000000 177 ns/op 0 B/op 0 allocs/op
BenchmarkSmallFilterQuery-8 10000000 133 ns/op 0 B/op 0 allocs/op
BenchmarkSmallFilterQueryWithRefresh-8 10000000 206 ns/op 0 B/op 0 allocs/op
BenchmarkLargeFilterAdd-8 5000000 252 ns/op 0 B/op 0 allocs/op
BenchmarkLargeFilterAddWithRefresh-8 5000000 325 ns/op 0 B/op 0 allocs/op
BenchmarkLargeFilterQuery-8 3000000 431 ns/op 0 B/op 0 allocs/op
BenchmarkLargeFilterQueryWithRefresh-8 2000000 543 ns/op 0 B/op 0 allocs/op
Contributors
Bogdan-Ciprian Rusu - Author/Maintainer
License
The project is licensed under the MIT License.
Documentation
¶
Index ¶
- func CalculateFalsePositiveRate(k, l uint) float64
- type Filter
- type Snapshot
- func (*Snapshot) Descriptor() ([]byte, []int)
- func (m *Snapshot) GetBase() uint64
- func (m *Snapshot) GetBuffer() []byte
- func (m *Snapshot) GetCount() uint64
- func (m *Snapshot) GetG() uint64
- func (m *Snapshot) GetK() uint64
- func (m *Snapshot) GetL() uint64
- func (m *Snapshot) GetR() uint64
- func (*Snapshot) ProtoMessage()
- func (m *Snapshot) Reset()
- func (m *Snapshot) String() string
- func (m *Snapshot) XXX_DiscardUnknown()
- func (m *Snapshot) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)
- func (m *Snapshot) XXX_Merge(src proto.Message)
- func (m *Snapshot) XXX_Size() int
- func (m *Snapshot) XXX_Unmarshal(b []byte) error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CalculateFalsePositiveRate ¶
CalculateFalsePositiveRate computes the false positive rate for given k and l parameters.
Types ¶
type Filter ¶
type Filter struct {
// contains filtered or unexported fields
}
Filter represents the Age-Partitioned Bloom Filter (APBF). The implementation is safe for concurrent use.
func NewFromSnapshot ¶
NewFromSnapshot recreates the matching filter from the provided snapshot.
func NewWithRefresh ¶
NewWithRefresh returns the APBF with k + l slices, g generation size, and r refresh interval.
func (*Filter) MaxCapacity ¶
MaxCapacity returns filter max capacity.
func (*Filter) MaxGenerations ¶
MaxGenerations returns filter max generations count.
func (*Filter) NextGeneration ¶
func (f *Filter) NextGeneration()
NextGeneration transitions to next generation.
type Snapshot ¶
type Snapshot struct {
K uint64 `protobuf:"varint,1,opt,name=k,proto3" json:"k,omitempty"`
L uint64 `protobuf:"varint,2,opt,name=l,proto3" json:"l,omitempty"`
G uint64 `protobuf:"varint,3,opt,name=g,proto3" json:"g,omitempty"`
R uint64 `protobuf:"varint,4,opt,name=r,proto3" json:"r,omitempty"`
Base uint64 `protobuf:"varint,5,opt,name=base,proto3" json:"base,omitempty"`
Count uint64 `protobuf:"varint,6,opt,name=count,proto3" json:"count,omitempty"`
Buffer []byte `protobuf:"bytes,7,opt,name=buffer,proto3" json:"buffer,omitempty"`
XXX_NoUnkeyedLiteral struct{} `json:"-"`
XXX_unrecognized []byte `json:"-"`
XXX_sizecache int32 `json:"-"`
}
func (*Snapshot) Descriptor ¶
func (*Snapshot) ProtoMessage ¶
func (*Snapshot) ProtoMessage()
func (*Snapshot) XXX_DiscardUnknown ¶
func (m *Snapshot) XXX_DiscardUnknown()
Source Files