𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Histogram approximation of frequency spectra with the use of moments

✍ Scribed by S. Dvořák

Book ID
112602339
Publisher
Springer
Year
1970
Tongue
English
Weight
309 KB
Volume
20
Category
Article
ISSN
0011-4626

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Space Complexity of Approximating th
The Space Complexity of Approximating the Frequency Moments
✍ Noga Alon; Yossi Matias; Mario Szegedy 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 172 KB

The frequency moments of a sequence containing m i elements of type i, 1 i n, are the numbers F k = n i=1 m k i . We consider the space complexity of randomized algorithms that approximate the numbers F k , when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it