Title: Cardinality Estimation
Abstract: This talk surveys research on a fundamental elementary problem: Estimate the number of different values in a data stream. This is a classical application of hashing, but in typical applications where memory is severely limited, more sophisticated algorithms are needed. This problem represents a fascinating case study of the use of the scientific analysis of algorithms to develop an important part of our computational infrastructure.