Approximation of Nonintegral Frequency Moments
This item is restricted to only allow viewing of the metadata.
Title
Approximation of Nonintegral Frequency Moments
Author
Pilz , Brian Scott
Advisors
Kalpakis , Konstantinos ;
Program
Computer Science
UMBC Department
Computer Science and Electrical Engineering
Document Type
thesis
Sponsors
University of Maryland , Baltimore County (UMBC)
Keywords
algorithms ; entropy ; frequency moments ; sketch ; stream
Date Issued
2011-01-01
Abstract
Let a data stream have length m over an alphabet of n letters , with letter i occurring m_i times for i = 1,...,n : For any k , define the frequency moments F_k as F_k =sum_{i=1}^n m_i^k . Alon , Matias , and Szegedy in 1999 showed how to estimate F_k for an integer k>=2 ; with a one-pass algorithm using O(n^{1-1/k} log(n)) space for given length m ; accuracy , and confidence . Here we extend those results to non-integral k ; obtaining bounds on the variance giving accuracy and confidence estimates , and giving quantitative results on the algorithm's space requirements , with particular interest to when k is near 1 . We also give some performance statistics of the algorithm for these cases , considering an application to entropy estimation . This algorithm of AMS is known as a sketching algorithm . Sketching algorithms are probabilistic algorithms generally requiring sublinear space vs . a classical O(n) (linear) space requirement , and may have applications for anomaly detection of systems or networks .
Identifier
10565
Format
application:pdf
Language
en
Collection
UMBC Theses and Dissertations .
Rights Statement
This item may be protected under Title 17 of the U.S. Copyright Law. It is made available by UMBC for non-commercial research and education. For permission to publish or reproduce, please see http://aok.lib.umbc.edu/specoll/repro.php or contact Special Collections at speccoll(at)umbc.edu.
Source
Pilz_umbc_0434M_10565.pdf
Access Rights
Access limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan through a local library, pending author/copyright holder's permission.
Add tags for Approximation of Nonintegral Frequency Moments
Your comment:
Your Name:
...
