count-distinct

countdistinct

Implementations of the count-distinct problem algorithms in Go.

Install

$ go get -u github.com/banaio/countdistinct/cmd/...
$ countdistinct --help
In computer science, the count-distinct problem (also
known in applied mathematics as the cardinality estimation
problem) is the problem of finding the number of distinct
elements in a data stream with repeated elements. This is
a well-known problem with numerous applications. The elements
might represent IP addresses of packets passing through a router,
unique visitors to a web site, elements in a large database,
motifs in a DNA sequence, or elements of RFID/sensor networks.

See: https://en.wikipedia.org/wiki/Count-distinct_problem

Usage:
  countdistinct [flags]

Flags:
  -a, --algorithm string   The algorithm to use (default "pcsa")
  -f, --file string        File containing the elements to add (default "/Users/mbana/dev/banaio/github/countdistinct/countdistinct-elements.txt")
  -h, --help               help for countdistinct

Reading

Probabilistic Counting with Stochastic Averaging (PCSA)

• Probabilistic Counting with Stochastic Averaging
• Sketch of the Day: Probabilistic Counting with Stochastic Averaging (PCSA)
• Flajolet–Martin algorithm
• Probabilistic Counting Algorithms for Data Base Applications