rydnr/pharopds

Probabilistic data structures in Pharo Smalltalk.

PharoPDS

The purpose of PharoPDS is to provide some probabilistic data structures and algorithms implemented in Pharo.

''Probabilistic data structures'' is a common name for data structures based mostly on different hashing techniques. Unlike regular and deterministic data structures, they always provide approximated answers but with reliable ways to estimate possible errors.

The potential losses and errors are fully compensated for by extremely low memory requirements, constant query time, and scaling. All these factors make these structures relevant in ''Big Data'' applications.

We've written some posts about the library and the historical and intellectual background of some ideas behind the approach we have followed:

• Understanding Bloom filters with Pharo Smalltalk
• Designing media for thought with moldable development

Install PharoPDS

To install PharoPDS on your Pharo image you can just find it in the Pharo Project Catalog (World menu > Tools > Catalog Browser) and click in the green mark icon in the upper right corner to install the latest stable version:

Or, you can also execute the following script:

    Metacello new
      baseline: #ProbabilisticDataStructures;
    	repository: 'github://osoco/PharoPDS:master/src';
    	load

You can optionally install all the custom extensions and interactive tutorials included with the project executing the following script to install the group 'All':

    Metacello new
      baseline: #ProbabilisticDataStructures;
    	repository: 'github://osoco/PharoPDS:master/src';
    	load: 'All'

To add PharoPDS to your own project's baseline just add this:

    spec
    	baseline: #ProbabilisticDataStructures
    	with: [ spec repository: 'github://osoco/PharoPDS:master/src' ]

Note that you can replace the master by another branch or a tag.

Data Structures

Currently, PharoPDS provides probabilistic data structures for the following categories of problems:

Membership

A membership problem for a dataset is a task to decide whether some elements belongs to the dataset or not.

The data structures provided to solve the membership problem are the following:

• Bloom Filter.

Cardinality

This is still a work in progress.

• HyperLogLog

Moldable development

This library has been developed trying to apply the ideas after the moldable development approach, so you can expect that each data structure provides its own custom and domain-specific extensions in order to ease the understanding and learning by the developers.

For instance, the following pictures are some of the extensions provided by the Bloom filter:

Algorithms Browser

In order to ease the understanding of the inner workings and trade-offs, we provide specific Playground tools for each data structure that allows the developer to explore it and get deeper insights.

You can browse the available algorithm playgrounds through the PharoPDS Algorithms Browser. You can open it with the following expression:

PDSAlgorithmsBrowser open 

License

PharoPDS is written and supported by developers at OSOCO and published as free and open source software under an MIT license.

Project dependencies

Hashing plays a central role in probabilistic data structures. Indeed, the choice of the appropiate hash functions is crucial to avoid bias and to reach a good performance. In particular, the structures require non-cryptographic hash functions that are provided by the dependency module NonCryptographicHashes.

Other dependencies like Roassal or GToolkit are optional for production use. Nevertheless, we recommend that you install them in the development image if you want to get some useful tools like Inspector custom extensions, the algorithm browser or interactive tutorials.