diff --git a/metadata/entries/Frequency_Moments.toml b/metadata/entries/Frequency_Moments.toml --- a/metadata/entries/Frequency_Moments.toml +++ b/metadata/entries/Frequency_Moments.toml @@ -1,44 +1,45 @@ title = "Formalization of Randomized Approximation Algorithms for Frequency Moments" date = 2022-04-08 topics = [ "Computer science/Algorithms/Approximation", "Mathematics/Probability theory", ] abstract = """ In 1999 Alon et. al. introduced the still active research topic of approximating the frequency moments of a data stream using randomized algorithms with minimal space usage. This includes the problem of estimating the cardinality of the stream elements - the zeroth frequency moment. But, also higher-order frequency moments that provide information about the skew of the data stream. (The k-th frequency moment of a data stream is the sum of the k-th powers of the occurrence counts of each element in the stream.) This entry formalizes three randomized algorithms for the approximation of F0, F2 and Fk for k ≥ 3 based on [1, 2] and verifies their expected accuracy, success probability and space usage.""" license = "bsd" note = "" [authors] [authors.karayel] homepage = "karayel_homepage" [contributors] [notify] karayel = "karayel_email" [history] [extra] [related] +dois = ["10.4230/LIPIcs.ITP.2022.21"]