2010 · 323 citations · 29 references
ComputingComputer ScienceMathematicsAlgorithmsData MiningOptimizationAlgorithm AnalysisAlgorithmic ComplexityApproximation AlgorithmsComputational ComplexityRoutingStreaming AlgorithmsData Stream MiningDistinct Elements CountingDistinct Elements EstimationStream Mining
This problem has applications to query optimization, Internet routing, network topology, and data mining. The authors present the first optimal algorithm for estimating the number of distinct elements in a data stream, addressing a longstanding theoretical problem. The algorithm achieves a (1 ± ε)-approximation using O(1/ε² + log n) bits of space and 2/3 success probability, with the probability amplifiable by independent repetition. The algorithm processes each update in O(1) worst‑case time and can report an estimate at any point in O(1) worst‑case time, thereby resolving both space and time complexity simultaneously.
We give the first optimal algorithm for estimating the number of distinct elements in a data stream, closing a long line of theoretical research on this problem begun by Flajolet and Martin in their seminal paper in FOCS 1983. This problem has applications to query optimization, Internet routing, network topology, and data mining. For a stream of indices in {1,...,n}, our algorithm computes a (1 ± ε)-approximation using an optimal O(1/ε-2 + log(n)) bits of space with 2/3 success probability, where 0<ε<1 is given. This probability can be amplified by independent repetition. Furthermore, our algorithm processes each stream update in O(1) worst-case time, and can report an estimate at any point midstream in O(1) worst-case time, thus settling both the space and time complexities simultaneously.
29
Universal classes of hash functions
J.Lawrence Carter, Mark N. Wegman · Journal of Computer and System Sciences · 1979 · 2.6K citations
Access path selection in a relational database management system
Patricia G. Selinger, M. M. Astrahan, Donald D. Chamberlin et al. · 1979 · 2.2K citations