f0

README

f0

An implementation of the CVM algorithm for the distinct elements (f0) problem.

This package implements the CVM algoritm in pure Go. CVM is an algorithm for the distinct elements problem. When you're trying to find the unique elements in a slice, but the slice exceeds the amount of available memory, use f0 to estimate the number of unique elements in said slice.

f0.Estimate(mySlice, 0.01, 0.001) // 329.4221234

More Reading

• Computer Scientists Invent an Efficient New Way to Count

Contributing

I NEED tests. The problem with this algorithm is that I need large sets of comparable elements to test f0 on. Currently (below v1), there is no guarentee the algorithm will work correctly. After we've developed a large and robust test suite and can establish the algorithm is behaving as expected, this library will be promoted to v1 and maintained.

The Bible is included for testing purposes. There's no copyright in the Kingdom of Heaven.

Documentation

Overview

f0 is an implementation of the CVM algorithm for the distinct elements problem.

• https://arxiv.org/abs/2301.10191

The CVM algorithm is best suited for large datasets where sorting unique values would require more than available memory.

Index

• func Estimate[T comparable](source []T, e, d float64) float64

Functions

func Estimate

func Estimate[T comparable](source []T, e, d float64) float64

Estimate uses the CVM algorithm to calculate the number of unique item in an array. e (epsilon) represents acceptable relative error d (delta) represents the probability of failure for the algorithm to produce an estimation within the specific e-bound.