pdsa 0.3.0

Introduction

Probabilistic data structures is a common name of data structures based on different hashing techniques.

Unlike regular (or deterministic) data structures, they always provide approximated answers, but usually with reliable ways to estimate the error probability.

The potential losses or errors are fully compensated by extremely low memory requirements, constant query time and scaling.

GitHub repository: https://github.com/gakhov/pdsa

Dependencies

• Python 3.3+ (http://python.org/download/)

• Cython 0.25+ (http://cython.org/#download)

Documentation

The latest documentation can be found at http://pdsa.readthedocs.io/en/latest/

Membership problem

• Bloom Filter

• Counting Bloom Filter

Cardinality problem

• Linear counter

• Probabilistic counter (Flajolet–Martin algorithm)

Rank problem

• q-digest

License

MIT License

Source code

• https://github.com/gakhov/pdsa/

Authors

• Maintainer: Andrii Gakhov <andrii.gakhov@gmail.com>

Install with pip

Installation requires a working build environment.

Using pip, PDSA releases are currently only available as source packages.

$ pip3 install -U pdsa

When using pip it is generally recommended to install packages in a virtualenv to avoid modifying system state:

$ virtualenv .env -p python3 --no-site-packages
$ source .env/bin/activate
$ pip3 install -U cython
$ pip3 install -U pdsa

Compile from source

The other way to install PDSA is to clone its GitHub repository and build it from source.

$ git clone https://github.com/gakhov/pdsa.git
$ cd pdsa

$ make build

$ bin/pip3 install -r requirements-dev.txt
$ make tests