quicksilver

quicksilver copied to clipboard

Overview

Quicksilver is a library of approximate algorithm and sketches

The algorithms contained within this library are designed to calculate common metrics and statistics (such as cardinality, frequency, etc) in an approximate fashion. In exchange for decreased accuracy, these algorithms typically have minimal memory overhead or are very fast. Or both.

Build status with Rust Nightly:

##Documentation

API Docs are auto-generated after every commit: http://www.rust-ci.org/polyfractal/quicksilver/doc/quicksilver/

Public modules

HLL - HyperLogLog

Approximates cardinality estimation with minimal memory overhead

This implements HyperLogLog, an algorithm which provides a reasonably accurate estimation of cardinality. It is very fast (200m op/s on my Macbook Air) and requires minimal memory. It can estimate the cardinality of sets that contain billions of entries.

See this article for a good laymen explanation of HyperLogLog.

Usage

use quicksilver::hll::HLL;
use std::hash::Hash;

let mut hll = HLL::new(12);

for i in range(0u, 1000000) {
  let hash = hash::hash(&i);
  hll.offer_hashed(&hash);
}

let cardinality = hll.cardinality();

Precision vs Memory chart

PCSA - Probabilistic Counting with Stochastic Averaging

Implements the Probabilistic Counting with Stochastic Averaging counter. PCSA provides an approximate estimate of cardinality with bounded error. Relative error is 0.78 / sqrt(m)

See this article for a layman's explanation of PCSA

Original paper can be found here

Note: PCSA is generally inferior to HLL in estimation accuracy, memory usage and performance

Usage

use quicksilver::pcsa::PCSA;
use std::hash::Hash;

let mut hll = PCSA::new(10);

for i in range(0u, 1000000) {
  let hash = hash::hash(&i);
  pcsa.offer_hashed(hash);
}

let cardinality = pcsa.cardinality();

Precision vs Memory chart