Streaming Algorithm - Some Streaming Problems - Entropy

Entropy

The (empirical) entropy of a set of frequencies is defined as F_k(\mathbf{a}) = \sum_{i=1}^n \frac{a_i}{m}\log{\frac{a_i}{m}}, where .

Estimation of this quantity in a stream has been done by:

  • McGregor et al.
  • Do Ba et al.
  • Lall et al.
  • Chakrabarti et al.

Read more about this topic:  Streaming Algorithm, Some Streaming Problems

Famous quotes containing the word entropy:

    “Just as the constant increase of entropy is the basic law of the universe, so it is the basic law of life to be ever more highly structured and to struggle against entropy.”
    —Václav Havel (b. 1936)