pds

pdsa

Probabilistic Data Structures and Algorithms in Python

Showing:

Popularity

Downloads/wk

0

GitHub Stars

76

Maintenance

Last Commit

2yrs ago

Contributors

5

Package

Dependencies

0

License

MIT

Categories

Readme

PDSA: Probabilistic Data Structures and Algorithms in Python


.. image:: https://img.shields.io/travis/gakhov/pdsa/master.svg?style=flat-square :target: https://travis-ci.org/gakhov/pdsa :alt: Travis Build Status

.. image:: https://img.shields.io/github/release/gakhov/pdsa/all.svg?style=flat-square :target: https://github.com/gakhov/pdsa/releases :alt: Current Release Version

.. image:: https://img.shields.io/pypi/v/pdsa.svg?style=flat-square :target: https://pypi.python.org/pypi/pdsa :alt: pypi Version

.. image:: https://readthedocs.org/projects/pdsa/badge/?version=latest&style=flat-square :target: http://pdsa.readthedocs.io/en/latest/ :alt: Documentation Version

.. image:: https://img.shields.io/pypi/pyversions/pdsa.svg?style=flat-square :target: https://github.com/gakhov/pdsa :alt: Python versions

.. contents ::

The Book

Everybody interested in learning more about probabilistic data structures and algorithms could be referred to our recently published book:

Probabilistic Data Structures and Algorithms for Big Data Applications <https://pdsa.gakhov.com>_ by Andrii Gakhov

2019, ISBN: 978-3748190486 (paperback) ASIN: B07MYKTY8W (e-book)

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

Documentation

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

Membership problem

  • Bloom Filter <http://pdsa.readthedocs.io/en/latest/membership/bloom_filter.html>_
  • Counting Bloom Filter <http://pdsa.readthedocs.io/en/latest/membership/counting_bloom_filter.html>_

Cardinality problem

  • Linear counter <http://pdsa.readthedocs.io/en/latest/cardinality/linear_counter.html>_
  • Probabilistic counter (Flajolet–Martin algorithm) <http://pdsa.readthedocs.io/en/latest/cardinality/probabilistic_counter.html>_
  • HyperLogLog <http://pdsa.readthedocs.io/en/latest/cardinality/hyperloglog.html>_

Frequency problem

  • Count Sketch <http://pdsa.readthedocs.io/en/latest/frequency/count_sketch.html>_
  • Count-Min Sketch <http://pdsa.readthedocs.io/en/latest/frequency/count_min_sketch.html>_

Rank problem

  • Random Sampling <http://pdsa.readthedocs.io/en/latest/rank/random_sampling.html>_
  • q-digest <http://pdsa.readthedocs.io/en/latest/rank/qdigest.html>_

License

MIT License

Source code

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.

.. code:: bash

$ pip3 install -U pdsa

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

.. code:: bash

$ 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 <https://github.com/gakhov/pdsa>_ and build it from source.

.. code:: bash

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

$ make install

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

Rate & Review

Great Documentation0
Easy to Use0
Performant0
Highly Customizable0
Bleeding Edge0
Responsive Maintainers0
Poor Documentation0
Hard to Use0
Slow0
Buggy0
Abandoned0
Unwelcoming Community0
100
No reviews found
Be the first to rate

Alternatives

No alternatives found

Tutorials

No tutorials found
Add a tutorial