bloom-filter

License	MIT
GroupId	com.github.alexandrnikitin
ArtifactId	bloom-filter_2.13
Last Version	0.13.1
Release Date	Apr 28, 2020
Type	jar
Description	bloom-filter bloom-filter
Project URL	https://github.com/alexandrnikitin/bloom-filter-scala
Project Organization	com.github.alexandrnikitin
Source Code Management	https://github.com/alexandrnikitin/bloom-filter-scala

Download bloom-filter_2.13

Filename	Size
bloom-filter_2.13-0.13.1.pom
bloom-filter_2.13-0.13.1.jar	60 KB
bloom-filter_2.13-0.13.1-sources.jar	9 KB
bloom-filter_2.13-0.13.1-javadoc.jar	1 MB

How to add to project

Apache Maven

<!-- https://jarcasting.com/artifacts/com.github.alexandrnikitin/bloom-filter_2.13/ -->
<dependency>
    <groupId>com.github.alexandrnikitin</groupId>
    <artifactId>bloom-filter_2.13</artifactId>
    <version>0.13.1</version>
</dependency>

Gradle Groovy

// https://jarcasting.com/artifacts/com.github.alexandrnikitin/bloom-filter_2.13/
implementation 'com.github.alexandrnikitin:bloom-filter_2.13:0.13.1'

Gradle Kotlin

// https://jarcasting.com/artifacts/com.github.alexandrnikitin/bloom-filter_2.13/
implementation ("com.github.alexandrnikitin:bloom-filter_2.13:0.13.1")

Apache Buildr

'com.github.alexandrnikitin:bloom-filter_2.13:jar:0.13.1'

Apache Ivy

<dependency org="com.github.alexandrnikitin" name="bloom-filter_2.13" rev="0.13.1">
  <artifact name="bloom-filter_2.13" type="jar" />
</dependency>

Groovy Grape

@Grapes(
@Grab(group='com.github.alexandrnikitin', module='bloom-filter_2.13', version='0.13.1')
)

Scala SBT

libraryDependencies += "com.github.alexandrnikitin" % "bloom-filter_2.13" % "0.13.1"

Leiningen

[com.github.alexandrnikitin/bloom-filter_2.13 "0.13.1"]

Dependencies

compile (1)

Group / Artifact	Type	Version
org.scala-lang : scala-library	jar	2.13.1

Project Modules

There are no modules declared in this project.

Bloom filter for Scala

Overview

"A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not. In other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed," says Wikipedia.

What's Bloom filter in a nutshell:

• Optimization for memory. It comes into play when you cannot put whole set into memory.
• Solves the membership problem. It can answer one question: does an element belong to a set or not?
• Probabilistic (lossy) data structure. It can answer that an element probably belongs to a set with some probability.

Getting Started

libraryDependencies += "com.github.alexandrnikitin" %% "bloom-filter" % "latest.release"

// Create a Bloom filter
val expectedElements = 1000000
val falsePositiveRate = 0.1
val bf = BloomFilter[String](expectedElements, falsePositiveRate)

// Put an element
bf.add(element)

// Check whether an element in a set
bf.mightContain(element)

// Dispose the instance
bf.dispose()

Motivation

You can read about this Bloom filter and motivation behind in my blog post

Benchmarks

Here's a benchmark for the String type and results for other types are very similar to these:

[info] Benchmark                                              (length)   Mode  Cnt          Score         Error  Units
[info] alternatives.algebird.StringItemBenchmark.algebirdGet      1024  thrpt   20    1181080.172 ▒    9867.840  ops/s
[info] alternatives.algebird.StringItemBenchmark.algebirdPut      1024  thrpt   20     157158.453 ▒     844.623  ops/s
[info] alternatives.breeze.StringItemBenchmark.breezeGet          1024  thrpt   20    5113222.168 ▒   47005.466  ops/s
[info] alternatives.breeze.StringItemBenchmark.breezePut          1024  thrpt   20    4482377.337 ▒   19971.209  ops/s
[info] alternatives.guava.StringItemBenchmark.guavaGet            1024  thrpt   20    5712237.339 ▒  115453.495  ops/s
[info] alternatives.guava.StringItemBenchmark.guavaPut            1024  thrpt   20    5621712.282 ▒  307133.297  ops/s

[info] bloomfilter.mutable.StringItemBenchmark.myGet              1024  thrpt   20   11483828.730 ▒  342980.166  ops/s
[info] bloomfilter.mutable.StringItemBenchmark.myPut              1024  thrpt   20   11634399.272 ▒   45645.105  ops/s
[info] bloomfilter.mutable._128bit.StringItemBenchmark.myGet      1024  thrpt   20   11119086.965 ▒   43696.519  ops/s
[info] bloomfilter.mutable._128bit.StringItemBenchmark.myPut      1024  thrpt   20   11303765.075 ▒   52581.059  ops/s

Basically, this implementation is 2x faster than Google's Guava and 10-80x than Twitter's Algebird. Other benchmarks you can find in the "benchmarks' module on github

Warning: These are synthetic benchmarks in isolated environment. Usually the difference in throughput and latency is bigger in production system because it will stress the GC, lead to slow allocation paths and higher latencies, trigger the GC, etc.

Versions

Version
0.13.1 Apr 28, 2020
0.13.0 Apr 25, 2020
0.12.0 Apr 2, 2020