Max & Min

This is really easy: keep track of the max.

function Streamath() {
  this.max = 0;
}

Streamath.prototype.feed = function feed(value) {
  if(this.max < value) {
    this.max = value;
  }
}

// Let's create random numbers
function random(min, max) {
  return function() {
    var r = Math.random() * (max - min) + min;
    return r*r*r*r*r*r*r; // <- Make distribution lower!
  }
}

var c = 0;
// Input yields a result of random(0,1) every 10ms to the function
var i = new Input(10, random(0,1), function(number) {
  streamath.feed(number);
  c += 1;
  console.log(c, number, streamath.max); // Outpout for GNUPlot
});

This algorithm knows too much!

Let's inoculate Alzheimer.

function Streamath() {
  this.max = 0;
  this.amortized = 0;
  this.idx = 0;
}

Streamath.prototype.feed = function feed(value) {
  this.idx += 1;
  if(this.amortized < value + this.idx) {
    this.max = value;
    this.amortized = value + this.idx;
  }
}

Average

Sum values

Count values

Keep running counts!

function Streamath() {
  /* Keep running counts */
  this.count = 0;
  this.sum = 0;
}

Streamath.prototype.feed = function feed(value) {
  this.count += 1;
  this.sum += value
}

Streamath.prototype.average = function average() {
  if(this.count)
    return this.sum/this.count
  return null;
}

function random(min, max) {
  return function() {
    return Math.random() * (max - min) + min;
  }
}

// Input yields a result of random(0,100) every 1ms to the function
new Input(1, random(0,100), function(number) {
  streamath.feed(number);
});

// Guess what? The average quickly converges to 50!

Let's try another distribution

Old values are here forever... and average become flat over time.

Recursive average to the rescue

AVG(t-1) * weight + value(t)

weight + 1

The weight of old values quickly fades in, based on the weight. We're computing running averages, without windowing

StandardDeviation

Variance is the average of the distance to the average

1/N * ∑(k−avg)

In other words: we need to recompute all the distances evertime we have a new value for the average *(

Maths to the rescue!

1/N * ∑(k−avg)

is the same as (König-Huygens)

1/N * ∑k^2 - avg^2

function Streamath() {
  this.count = 0;
  this.sum = 0;
  this.sqr = 0; // <- Keep a new rolling number: the sum of squares
}

Streamath.prototype.feed = function feed(value) {
  this.count += 1;
  this.sum += value;
  this.sqr += value * value; // <- Update the sum of square
}

Streamath.prototype.average = function average() {
  if(this.count)
    return this.sum/this.count
  return null;
}

Streamath.prototype.stddev = function stddev() {
  var avg = this.average();
  if(this.count)
    return Math.sqrt(this.sqr/this.count - avg * avg);
  return null;
}

Medians and percentiles

Tale of 2 heaps

• Keep 2 heaps: greater numbers and smaller numbers
• If the new number is greater than the median, insert in the great number heap, at the right place
• If the new number is lower than the median, insert in the smaller number heap, at the right place
• If either heap's length is larger than the other one by more than 1, rebalance
• Median is smallest of greater numbers
• It is possible to 'clean up the heaps' simultaneously by their ends.

Membership

Bloom Filters

• space-efficient probabilistic data structure
• Multiple hashes, for multiple dimensions
• False positive possible, but no false negative
• 10 bits per element are required for a 1% false positive probability

Shamelessly stolen from http://www.jasondavies.com/bloomfilter/

They fill up!

• Time-limit them
• Extend them
• Counting filters