TY - GEN
T1 - Modeling skew in data streams
AU - Korn, Flip
AU - Muthukrishnan, S.
AU - Wu, Yihua
PY - 2006
Y1 - 2006
N2 - Data stream applications have made use of statistical summaries to reason about the data using nonparametric tools such as histograms, heavy hitters, and join sizes. However, relatively little attention has been paid to modeling stream data parametrically, despite the potential this approach has for mining the data. The challenges to do model fitting at streaming speeds are both technical - how to continually find fast and reliable parameter estimates on high speed streams of skewed data using small space - and conceptual - how to validate the goodness-of-fit and stability of the model online.In this paper, we show how to fit hierarchical (binomial multifractal) and non-hierarchical (Pareto) power-law models on a data stream. We address the technical challenges using an approach that maintains a sketch of the data stream and fits least-squares straight lines; it yields algorithms that are fast, space-efficient, and provide approximations of parameter value estimates with a priori quality guarantees relative to those obtained offline. We address the conceptual challenge by designing fast methods for online goodness-of-fit measurements on a data stream; we adapt the statistical testing technique of examining the quantile-quantile (q-q) plot, to perform online model validation at streaming speeds.As a concrete application of our techniques, we focus on network traffic data which has been shown to exhibit skewed distributions. We complement our analytic and algorithmic results with experiments on IP traffic streams in AT&T's Gigascope data stream management system, to demonstrate practicality of our methods at line speeds. We measured the stability and robustness of these models over weeks of operational packet data in an IP network. In addition, we study an intrusion detection application, and demonstrate the potential of online parametric modeling.
AB - Data stream applications have made use of statistical summaries to reason about the data using nonparametric tools such as histograms, heavy hitters, and join sizes. However, relatively little attention has been paid to modeling stream data parametrically, despite the potential this approach has for mining the data. The challenges to do model fitting at streaming speeds are both technical - how to continually find fast and reliable parameter estimates on high speed streams of skewed data using small space - and conceptual - how to validate the goodness-of-fit and stability of the model online.In this paper, we show how to fit hierarchical (binomial multifractal) and non-hierarchical (Pareto) power-law models on a data stream. We address the technical challenges using an approach that maintains a sketch of the data stream and fits least-squares straight lines; it yields algorithms that are fast, space-efficient, and provide approximations of parameter value estimates with a priori quality guarantees relative to those obtained offline. We address the conceptual challenge by designing fast methods for online goodness-of-fit measurements on a data stream; we adapt the statistical testing technique of examining the quantile-quantile (q-q) plot, to perform online model validation at streaming speeds.As a concrete application of our techniques, we focus on network traffic data which has been shown to exhibit skewed distributions. We complement our analytic and algorithmic results with experiments on IP traffic streams in AT&T's Gigascope data stream management system, to demonstrate practicality of our methods at line speeds. We measured the stability and robustness of these models over weeks of operational packet data in an IP network. In addition, we study an intrusion detection application, and demonstrate the potential of online parametric modeling.
KW - Estimation
KW - Modeling
KW - Skew
KW - Streaming algorithms
UR - http://www.scopus.com/inward/record.url?scp=34250648954&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34250648954&partnerID=8YFLogxK
U2 - 10.1145/1142473.1142495
DO - 10.1145/1142473.1142495
M3 - Conference contribution
AN - SCOPUS:34250648954
SN - 1595934340
SN - 9781595934345
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
SP - 181
EP - 192
BT - SIGMOD 2006 - Proceedings of the ACM SIGMOD International Conference on Management of Data
T2 - 2006 ACM SIGMOD International Conference on Management of Data
Y2 - 27 June 2006 through 29 June 2006
ER -