Probabilistic data structures

## 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).

### 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.

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..

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.

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

## Project details

### 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