Skip to main content

Probabilistic data structures

Project description

Probabilistic Structures

Probstructs is easy to use Python wrapper for C++ library probstructs . It supports Exponential Histograms, Count Min Sketch (CM-Sketch), and Exponential Count Min Sketch (ECM-Sketch).

build status Documentation Status Version Py Versions GitHub stars

Installation

With pip:

pip install probstructs

From source:

pip install .

Classes

CountMinSketch

Count–min sketch (CM sketch) is a probabilistic data structure that serves as a frequency table of events in a stream of data. It uses hash functions to map events to frequencies, but unlike a hash table uses only sub-linear space, at the expense of overcounting some events due to collisions.

C++ documentation: https://probstructs.readthedocs.io/en/latest/classes.html#countminsketch

from probstructs import CountMinSketch

cm_sketch = CountMinSketch(100, 4)
cm_sketch.inc("aaa", 1)
cm_sketch.inc("bbb", 5)
cm_sketch.inc("aaa", 2)

print(cm_sketch.get("aaa"))
# 3
print(cm_sketch.get("bbb"))
# 5
print(cm_sketch.get("ccc"))
# 0


cm_sketch = CountMinSketch(width=100, depth=4)
cm_sketch.inc(key="bbb", delta=5)
print(cm_sketch.get(key="bbb"))
# 5

ExponentialHistorgram

Exponential histogram (EH) is a probabilistic data structure that serves as a frequency counter for specific elements in the last N elements from stream..

C++ documentation: https://probstructs.readthedocs.io/en/latest/classes.html#exponentialhistorgram

from probstructs import ExponentialHistorgram


eh = ExponentialHistorgram(1)
eh.inc(1, 1)
print(eh.get(1, 1))
# 1
eh.inc(1, 1)
print(eh.get(1, 1))
# 2
eh.inc(2, 1)
print(eh.get(1, 2))
# 1

eh = ExponentialHistorgram(window=1)
eh.inc(tick=1, delta=1)
print(eh.get(window=1, tick=1))
# 1
eh.inc(tick=1, delta=1)
print(eh.get(window=1, tick=1))
# 2
eh.inc(tick=2, delta=1)
print(eh.get(window=1, tick=2))
# 1

ExponentialCountMinSketch

Exponential count-min sketch (ECM-Sketch) combines CM-Sketch with EH to count number of different elements in the last N elements in the stream.

C++ documentation: https://probstructs.readthedocs.io/en/latest/classes.html#exponentialcountminsketch

from probstructs import ExponentialCountMinSketch


ecm_sketch = ExponentialCountMinSketch(100, 4, 8)

ts = 0
ecm_sketch.inc("aaa", ts, 1)
ecm_sketch.inc("bbb", ts, 4)
ecm_sketch.inc("ccc", ts, 8)

print(ecm_sketch.get("aaa", 4, ts))
# 1
print(ecm_sketch.get("bbb", 4, ts))
# 4
print(ecm_sketch.get("ccc", 4, ts))
# 8
print(ecm_sketch.get("ddd", 4, ts))
# 0

ecm_sketch = ExponentialCountMinSketch(width=100, depth=4, window=8)

ts = 0
ecm_sketch.inc(key="aaa", tick=ts, delta=1)
ecm_sketch.inc(key="bbb", tick=ts, delta=4)
ecm_sketch.inc(key="ccc", tick=ts, delta=8)

print(ecm_sketch.get(key="aaa", window=4, tick=ts))
# 1
print(ecm_sketch.get(key="bbb", window=4, tick=ts))
# 4
print(ecm_sketch.get(key="ccc", window=4, tick=ts))
# 8
print(ecm_sketch.get(key="ddd", window=4, tick=ts))
# 0

Changelog

0.2.0

  • Introduce named parameters

  • Update documentation to contain examples

0.1.0

  • Initial version

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

probstructs-0.2.8.tar.gz (8.4 kB view hashes)

Uploaded Source

Built Distributions

probstructs-0.2.8-pp39-pypy39_pp73-win_amd64.whl (71.9 kB view hashes)

Uploaded PyPy Windows x86-64

probstructs-0.2.8-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (559.1 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

probstructs-0.2.8-pp39-pypy39_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (599.6 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

probstructs-0.2.8-pp39-pypy39_pp73-macosx_10_9_x86_64.whl (78.6 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

probstructs-0.2.8-pp38-pypy38_pp73-win_amd64.whl (72.0 kB view hashes)

Uploaded PyPy Windows x86-64

probstructs-0.2.8-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (559.7 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

probstructs-0.2.8-pp38-pypy38_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (600.0 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

probstructs-0.2.8-pp38-pypy38_pp73-macosx_10_9_x86_64.whl (78.7 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

probstructs-0.2.8-pp37-pypy37_pp73-win_amd64.whl (72.0 kB view hashes)

Uploaded PyPy Windows x86-64

probstructs-0.2.8-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (564.9 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

probstructs-0.2.8-pp37-pypy37_pp73-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (610.4 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

probstructs-0.2.8-pp37-pypy37_pp73-macosx_10_9_x86_64.whl (78.7 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

probstructs-0.2.8-cp311-cp311-win_amd64.whl (72.9 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

probstructs-0.2.8-cp311-cp311-win32.whl (63.8 kB view hashes)

Uploaded CPython 3.11 Windows x86

probstructs-0.2.8-cp311-cp311-musllinux_1_1_x86_64.whl (3.2 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ x86-64

probstructs-0.2.8-cp311-cp311-musllinux_1_1_i686.whl (3.0 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ i686

probstructs-0.2.8-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

probstructs-0.2.8-cp311-cp311-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (1.5 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

probstructs-0.2.8-cp311-cp311-macosx_10_9_x86_64.whl (90.4 kB view hashes)

Uploaded CPython 3.11 macOS 10.9+ x86-64

probstructs-0.2.8-cp310-cp310-win_amd64.whl (73.1 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

probstructs-0.2.8-cp310-cp310-win32.whl (63.9 kB view hashes)

Uploaded CPython 3.10 Windows x86

probstructs-0.2.8-cp310-cp310-musllinux_1_1_x86_64.whl (3.2 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ x86-64

probstructs-0.2.8-cp310-cp310-musllinux_1_1_i686.whl (3.0 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ i686

probstructs-0.2.8-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

probstructs-0.2.8-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (1.5 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

probstructs-0.2.8-cp310-cp310-macosx_10_9_x86_64.whl (90.4 kB view hashes)

Uploaded CPython 3.10 macOS 10.9+ x86-64

probstructs-0.2.8-cp39-cp39-win_amd64.whl (73.2 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

probstructs-0.2.8-cp39-cp39-win32.whl (63.9 kB view hashes)

Uploaded CPython 3.9 Windows x86

probstructs-0.2.8-cp39-cp39-musllinux_1_1_x86_64.whl (3.2 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ x86-64

probstructs-0.2.8-cp39-cp39-musllinux_1_1_i686.whl (3.0 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ i686

probstructs-0.2.8-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

probstructs-0.2.8-cp39-cp39-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (1.5 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

probstructs-0.2.8-cp39-cp39-macosx_10_9_x86_64.whl (90.6 kB view hashes)

Uploaded CPython 3.9 macOS 10.9+ x86-64

probstructs-0.2.8-cp38-cp38-win_amd64.whl (72.8 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

probstructs-0.2.8-cp38-cp38-win32.whl (64.0 kB view hashes)

Uploaded CPython 3.8 Windows x86

probstructs-0.2.8-cp38-cp38-musllinux_1_1_x86_64.whl (3.2 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ x86-64

probstructs-0.2.8-cp38-cp38-musllinux_1_1_i686.whl (3.0 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ i686

probstructs-0.2.8-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

probstructs-0.2.8-cp38-cp38-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (1.5 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

probstructs-0.2.8-cp38-cp38-macosx_10_9_x86_64.whl (90.4 kB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

probstructs-0.2.8-cp37-cp37m-win_amd64.whl (73.3 kB view hashes)

Uploaded CPython 3.7m Windows x86-64

probstructs-0.2.8-cp37-cp37m-win32.whl (64.8 kB view hashes)

Uploaded CPython 3.7m Windows x86

probstructs-0.2.8-cp37-cp37m-musllinux_1_1_x86_64.whl (3.2 MB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ x86-64

probstructs-0.2.8-cp37-cp37m-musllinux_1_1_i686.whl (3.1 MB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ i686

probstructs-0.2.8-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ x86-64

probstructs-0.2.8-cp37-cp37m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (1.6 MB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

probstructs-0.2.8-cp37-cp37m-macosx_10_9_x86_64.whl (89.7 kB view hashes)

Uploaded CPython 3.7m macOS 10.9+ x86-64

probstructs-0.2.8-cp36-cp36m-win_amd64.whl (73.8 kB view hashes)

Uploaded CPython 3.6m Windows x86-64

probstructs-0.2.8-cp36-cp36m-win32.whl (65.1 kB view hashes)

Uploaded CPython 3.6m Windows x86

probstructs-0.2.8-cp36-cp36m-musllinux_1_1_x86_64.whl (3.2 MB view hashes)

Uploaded CPython 3.6m musllinux: musl 1.1+ x86-64

probstructs-0.2.8-cp36-cp36m-musllinux_1_1_i686.whl (3.1 MB view hashes)

Uploaded CPython 3.6m musllinux: musl 1.1+ i686

probstructs-0.2.8-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.17+ x86-64

probstructs-0.2.8-cp36-cp36m-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (1.6 MB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

probstructs-0.2.8-cp36-cp36m-macosx_10_9_x86_64.whl (89.8 kB view hashes)

Uploaded CPython 3.6m macOS 10.9+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page