|
IMC '05, 2005 Internet Measurement Conference — Abstract
Pp. 273–278 of the Proceedings
Improving Sketch Reconstruction Accuracy Using Linear Least Squares Method
Gene Moo Lee, Huiya Liu, Young Yoon, and Yin Zhang, University of Texas at Austin
Abstract
Sketch is a sublinear space data structure that allows one to
approximately reconstruct the value associated with any given key in
an input data stream. It is the basis for answering a number of
fundamental queries on data streams, such as range queries, finding
quantiles, frequent items, etc. In the networking context, sketch has
been applied to identifying heavy hitters and changes, which is
critical for traffic monitoring, accounting, and network anomaly
detection.
In this paper, we propose a novel approach called lsquare to
significantly improve the reconstruction accuracy of the sketch data
structure. Given a sketch and a set of keys, we estimate the values
associated with these keys by constructing a linear system and finding
the optimal solution for the system using linear least squares method.
We use a large amount of real Internet traffic data to evaluate
lsquare against countmin, the state-of-the-art sketch
scheme. Our results suggest that given the same memory requirement,
lsquare achieves much better reconstruction accuracy than
countmin. Alternatively, given the same reconstruction
accuracy, lsquare requires significantly less memory. This
clearly demonstrates the effectiveness of our approach.
- View the full text of this paper in HTML and PDF.
The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
|
Need help? Use our Contacts page.