Spacing-Saving algorithm

Spacing-Saving algorithm is an integrated approach for solving both problems of finding the most popular k elements, and finding frequent elements in a data stream.

Usage

// epsilon determines the total number of counters
ss, err := spaceSaving.NewStreamSummary(0.01)
if err != nil {
//...
}
ss.Record(item)

Acknowledge

1. Ahmed Metwally et al., Efficient computation of frequent and top-k elements in data streams . In Proceedings of the 10th international conference on Database Theory (ICDT'05)
2. Java Implementation of Spacing-Saving algorithm: https://github.com/fzakaria/space-saving