There is a big practicality problem I see with this algorithm. The thresh defined in the paper relies on the length of the stream. It seems to me that in a scenario where you have a big enough data set to desire a solution that doesn't just store every unique value you don't know the length. I did not make it through all the proofs but I believe they use the fact that the defined threshold has the length in it to prove error bounds. If I were to use this in a scenario where I need to know error bounds i would probably ballpark the length of my stream to estimate error bounds and then use the algorithm with a ballpark threshold depending on my systems memory.
Another practical thing is the "exception" if nothing is removed on line 6 in the original algorithm. This also seems needed for the proof but you would not want in production, though the chance of hitting it should be vanishingly small so maybe worth the gamble?
Here is my faithful interpretation of the algorithm. And then a re-interpretation with some "practical" improvements that almost certainly make the provability of the correctness impossible.
func CountUnique(scanner *bufio.Scanner, epsilon float64, delta float64, m int) int {
X := make(map[string]bool)
p := 1.0
thresh := int(math.Ceil((12 / (epsilon * epsilon)) \* math.Log(8*float64(m)/delta)))
for scanner.Scan() {
a := scanner.Text()
delete(X, a)
if rand.Float64() < p {
X[a] = true
}
if len(X) == thresh {
for key := range X {
if rand.Float64() < 0.5 {
delete(X, key)
}
}
p /= 2
if len(X) == thresh {
panic("Error")
}
}
}
return int(float64(len(X)) / p)
}
func CountUnique2(scanner *bufio.Scanner, thresh int) int {
//threshold passed in, based on system memory / estimates
X := make(map[string]bool)
p := 1.0
for scanner.Scan() {
a := scanner.Text()
delete(X, a)
if rand.Float64() < p {
X[a] = true
}
if len(X) >= thresh { // >= instead of == and remove the panic below
for key := range X {
if rand.Float64() < 0.5 {
delete(X, key)
}
}
p /= 2
}
}
return int(float64(len(X)) / p)
}
I tested it with Shakespeare's work. The actual unique word count is 71,595. With the second algorithm it is interesting to play with the threshold. Here are some examples.
threshold 1000
Mean Absolute Error: 2150.44
Root Mean Squared Error: 2758.33
Standard Deviation: 2732.61
threshold 2000
Mean Absolute Error: 1723.72
Root Mean Squared Error: 2212.74
Standard Deviation: 2199.39
threshold 10000
Mean Absolute Error: 442.76
Root Mean Squared Error: 556.74
Standard Deviation: 555.53
threshold 50000
Mean Absolute Error: 217.28
Root Mean Squared Error: 267.39
Standard Deviation: 262.84