@article{alonSpaceComplexityApproximating1999,
  title = {The {{Space Complexity}} of {{Approximating}} the {{Frequency Moments}}},
  volume = {58},
  issn = {00220000},
  url = {http://www.sciencedirect.com/science/article/pii/S0022000097915452},
  doi = {10.1006/jcss.1997.1545},
  abstract = {The frequency moments of a sequence containingmielements of typei, 1⩽i⩽n, are the numbersFk=∑ni=1mki. We consider the space complexity of randomized algorithms that approximate the numbersFk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF0,F1, andF2can be approximated in logarithmic space, whereas the approximation ofFkfork⩾6 requiresn\$Ømega\$(1)space. Applications to data bases are mentioned as well.},
  number = {1},
  journaltitle = {Journal of Computer and System Sciences},
  date = {1999},
  pages = {137--147},
  author = {Alon, Noga and Matias, Yossi and Szegedy, Mario},
  file = {/home/dimitri/Nextcloud/Zotero/storage/M7Z3C5AL/Alon, Matias, Szegedy - 1999 - The Space Complexity of Approximating the Frequency Moments.pdf}
}

{"_id":"TnsE3uKzgZpAGmMF9","bibbaseid":"alon-matias-szegedy-thespacecomplexityofapproximatingthefrequencymoments","authorIDs":[],"author_short":["Alon, N.","Matias, Y.","Szegedy, M."],"bibdata":{"bibtype":"article","type":"article","title":"The Space Complexity of Approximating the Frequency Moments","volume":"58","issn":"00220000","url":"http://www.sciencedirect.com/science/article/pii/S0022000097915452","doi":"10.1006/jcss.1997.1545","abstract":"The frequency moments of a sequence containingmielements of typei, 1⩽i⩽n, are the numbersFk=∑ni=1mki. We consider the space complexity of randomized algorithms that approximate the numbersFk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF0,F1, andF2can be approximated in logarithmic space, whereas the approximation ofFkfork⩾6 requiresn\\$Ømega\\$(1)space. Applications to data bases are mentioned as well.","number":"1","journaltitle":"Journal of Computer and System Sciences","date":"1999","pages":"137–147","author":[{"propositions":[],"lastnames":["Alon"],"firstnames":["Noga"],"suffixes":[]},{"propositions":[],"lastnames":["Matias"],"firstnames":["Yossi"],"suffixes":[]},{"propositions":[],"lastnames":["Szegedy"],"firstnames":["Mario"],"suffixes":[]}],"file":"/home/dimitri/Nextcloud/Zotero/storage/M7Z3C5AL/Alon, Matias, Szegedy - 1999 - The Space Complexity of Approximating the Frequency Moments.pdf","bibtex":"@article{alonSpaceComplexityApproximating1999,\n title = {The {{Space Complexity}} of {{Approximating}} the {{Frequency Moments}}},\n volume = {58},\n issn = {00220000},\n url = {http://www.sciencedirect.com/science/article/pii/S0022000097915452},\n doi = {10.1006/jcss.1997.1545},\n abstract = {The frequency moments of a sequence containingmielements of typei, 1⩽i⩽n, are the numbersFk=∑ni=1mki. We consider the space complexity of randomized algorithms that approximate the numbersFk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF0,F1, andF2can be approximated in logarithmic space, whereas the approximation ofFkfork⩾6 requiresn\\$Ømega\\$(1)space. Applications to data bases are mentioned as well.},\n number = {1},\n journaltitle = {Journal of Computer and System Sciences},\n date = {1999},\n pages = {137--147},\n author = {Alon, Noga and Matias, Yossi and Szegedy, Mario},\n file = {/home/dimitri/Nextcloud/Zotero/storage/M7Z3C5AL/Alon, Matias, Szegedy - 1999 - The Space Complexity of Approximating the Frequency Moments.pdf}\n}\n\n","author_short":["Alon, N.","Matias, Y.","Szegedy, M."],"key":"alonSpaceComplexityApproximating1999","id":"alonSpaceComplexityApproximating1999","bibbaseid":"alon-matias-szegedy-thespacecomplexityofapproximatingthefrequencymoments","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/S0022000097915452"},"downloads":0},"bibtype":"article","biburl":"https://raw.githubusercontent.com/dlozeve/newblog/master/bib/all.bib","creationDate":"2020-01-08T20:39:39.055Z","downloads":0,"keywords":[],"search_terms":["space","complexity","approximating","frequency","moments","alon","matias","szegedy"],"title":"The Space Complexity of Approximating the Frequency Moments","year":null,"dataSources":["3XqdvqRE7zuX4cm8m"]}