Skip to main content

Introduction

This is a python implementation of this paper, which proposes a heuristic algorithm for dynamic calculation of the median and other percentiles. It has the advantage of running in O(1) at each iteration and is hence particularly useful when dealing with continuously (and fastly) incoming data.

Install

  1. From sources

    git clone git@gitlab.octo.com:bdalab/psquare.git
    cd psquare
    python setup.py install
    
  2. Using pip

    pip install psquare
    

Example of use

In the following example, we will estimate the value of the 95th percentile of a N(0,1) distribution using p square algorithm. We will compare our estimates as we continuously draw from the distribution, by comparing with the truth value given by the numpy.percentile function. At the end, we will plot the residuals, and the execution time using psquare and numpy.percentile.

import numpy as np
import matplotlib
import matplotlib.pyplot as plt
import time

from psquare.psquare import PSquare

NB_ITERATIONS = 30000


def random_generator():
    return np.random.normal(0, 1, 1)


def exact_value_for_quantile(values, quantile):
    return np.percentile(values, quantile)


def main():
    values = [random_generator() for _ in range(5)]
    quantile_to_estimate = 95

    psquare = PSquare(quantile_to_estimate)
    exact_quantiles = []
    estimated_quantiles = []
    psquare_exec_time = []
    numpy_exec_time = []

    for val in values:  # p square algorithm necessitates 5 values to start
        psquare.update(val)

    for _ in range(NB_ITERATIONS):
        new_val = random_generator()
        values.append(new_val)

        psquare_start = time.time()
        psquare.update(new_val)
        estimated_quantiles.append(psquare.p_estimate())
        psquare_end = time.time()

        numpy_start = time.time()
        exact_quantiles.append(exact_value_for_quantile(values, quantile_to_estimate))
        numpy_end = time.time()

        psquare_exec_time.append(psquare_end - psquare_start)
        numpy_exec_time.append(numpy_end - numpy_start)

    matplotlib.rc('figure', figsize=(10, 5))
    errors = np.abs(np.array(estimated_quantiles) - np.array(exact_quantiles))
    plt.plot(errors)
    plt.title('Absolute error between p-square predicted value and exact percentile value')
    plt.ylabel('Difference between exact percentile value and p-square estimation')
    plt.xlabel('Size of the dataset')
    plt.rcParams["figure.figsize"] = (10, 5)
    plt.show()

    plt.plot(psquare_exec_time[1:], label='p-square')
    plt.plot(numpy_exec_time[1:], label='numpy percentile')
    plt.title('Execution time to compute percentile on a growing dataset')
    plt.ylabel('Execution time (in seconds)')
    plt.xlabel('Size of the dataset')
    plt.legend()
    plt.rcParams["figure.figsize"] = (10, 5)
    plt.show()


if __name__ == '__main__':
    main()

Error between estimated and exact value

Using previous example we obtain the following figures:

  • Errors between exact and predicted percentile value

  • Execution time between p-square estimations and numpy percentile function:

Metadata

Release files for psquare 1.1

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for psquare 1.1
File Size Uploaded Provenance Actions
psquare-1.1.tar.gz 3.9 kB Without provenance Details for psquare-1.1.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for psquare 1.1
File Interpreter ABI Platform Actions
psquare-1.1-py3-none-any.whl Python 3 none any Details for psquare-1.1-py3-none-any.whl

Total release size: 8.8 kB

Release files / psquare-1.1.tar.gz

Download URL psquare-1.1.tar.gz
Size 3.9 kB
Tags Source
SHA-256 checksum
How to use checksums
90c98c56606772620c96c2b07bf79433b02cb159c5553943f1fbdddd27bf10aa
BLAKE2b-256 checksum
How to use checksums
a31d5be857d68c4eb69d94b81dd96663570c2a685a3d8750ab44878a0f849856
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.1.0 pkginfo/1.5.0.1 requests/2.22.0 setuptools/42.0.1 requests-toolbelt/0.9.1 tqdm/4.39.0 CPython/3.7.3

Release files / psquare-1.1-py3-none-any.whl

Download URL psquare-1.1-py3-none-any.whl
Size 4.9 kB
Tags Python 3
SHA-256 checksum
How to use checksums
ef078241207335e65314ab9968b1f6a24cdfe6356ceb7286ef7f0135c262b19a
BLAKE2b-256 checksum
How to use checksums
16671f0cf584102f762d11d1e7fe3d565a2db4bf2558e08ce8e0b6688dd8f7ca
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.1.0 pkginfo/1.5.0.1 requests/2.22.0 setuptools/42.0.1 requests-toolbelt/0.9.1 tqdm/4.39.0 CPython/3.7.3

Security for psquare 1.1

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Release history Release notifications | RSS feed

This release

1.1 This release

2 release files No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page