More Web Proxy on the site http://driver.im/

research-article

Heavy hitters in streams and sliding windows

Authors:

Yaron KassnerAuthors Info & Claims

IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications

Pages 1 - 9

https://doi.org/10.1109/INFOCOM.2016.7524364

Published: 01 April 2016 Publication History

Abstract

Identifying heavy hitter flows is a fundamental problem in various network domains. The well established method of using sketches to approximate flow statistics suffers from space inefficiencies. In addition, flow arrival rates are dynamic, thus keeping track of the most recent heavy hitters poses a challenge. Sliding window approximations address this problem, reducing space at the cost of increasing point query time. This paper presents two novel algorithms for identifying heavy hitters in streams and sliding windows. Both algorithms use statically allocated memory and support constant time point queries. For sliding windows, this is an asymptotic improvement over previous work. We also demonstrate reduced memory requirements of up to 85% in streams and 66% in sliding windows over synthetic and real Internet packet traces.

References

[1]

The caida ucsd anonymized internet traces 2015 - february 19th, http://www.caida.org/data/passive/passive2015dataset.xml

[2]

Arasu, A., Manku, G.S.: Approximate counts and quantiles over sliding windows. In: Proc. of the 23rd ACM SIGACT-SIGMO D-SIGART Symp. on Principles of DB Systems, June 14-16, 2004. pp. 286–296

[3]

Ben-Basat, R., Einziger, G., Friedman, R., Kassner, Y.: Heavy hitters in streams and sliding windows. Tech. Rep. CS-2016-01, Computer Science, Technion (January 2016)

[4]

Cohen, S., Matias, Y.: Spectral bloom filters. In: Proc. of the ACM International Conference on Management of Data (SIGMOD) (2003)

[5]

Cormode, G., Hadjieleftheriou, M.: Finding frequent items in data streams. Proc. VLDB Endow. 1 (2), 1530–1541 (Aug 2008), code: www.research.att.com/marioh/frequent-items.html

[6]

Cormode, G., Muthukrishnan, S.: An improved data stream summary: The count-min sketch and its applications. J. Algorithms 55 (2004)

[7]

Demaine, E.D., López-Ortiz A., Munro, J.I.: Frequency estimation of internet packet streams with limited space. In: Proc. of the 10th Annual European Symposium on Algorithms. ESA, Springer-Verlag (2002)

[8]

Dimitropoulos, X., Hurley, P., Kind, A.: Probabilistic lossy counting: An efficient algorithm for finding heavy hitters. SIGCOMM Comput. Commun. Rev. 38 (1) (Jan 2008)

[9]

Dittmann, G., Herkersdorf, A.: Network processor load balancing for high-speed links. In: Proc. of the 2002 Int. Symp. on Performance Evaluation of Computer and Telecommunication Systems. vol. 735

[10]

Einziger, G., Friedman, R.: TinyLFU: A highly efficient cache admission policy. In: 22nd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2014). pp. 146–153

[11]

Einziger, G., Fellman, B., Kassner, Y.: Independent counter estimation buckets. The -34th Annual IEEE International Conference on Computer Communications (lNFOCOM 2015), Hong Kong, PR China (2015)

[12]

Einziger, G., Friedman, R.: Counting with TinyTable: Every Bit Counts! International Conference on Distributed Computing and Networking (ICDCN 2016)

[13]

Estan, C., Varghese G.: New directions in traffic measurement and accounting. SIGCOMM Comput. Commun. Rev. 32 (4) (Aug 2002)

[14]

Ficara, D., Pietro, A.D., Giordano, S., Procissi, G., Vitucci, F.: Enhancing counting bloom filters through huffman-coded multilayer structures. IEEE/ACM Trans. Netw. 18 (6), 1977–1987 (2010)

Digital Library

[15]

Garcia-Teodoro, P., Daz-Verdejo, J.E., Maci-Fernndez, G., Vzquez, E.: Anomaly-based network intrusion detection: Techniques, systems and challenges. Computers and Security pp. 18–28 (2009)

[16]

Hung, R.Y.S., Lee, L., Ting, H.: Finding frequent items over sliding windows with constant update time. Inf. Proc. Let.10' 110 (7), 257–260

[17]

Kabbani, A., Alizadeh, M., Yasuda, M., Pan, R., Prabhakar, B.: Af-qcn: Approximate fairness with quantized congestion notification for multi-tenanted data centers. In: Proc. of the 18th IEEE Symposium on High Performance Interconnects. HOTI (2010)

[18]

Karp, R.M., Shenker, S., Papadimitriou, C.H.: A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 28 (1) (Mar 2003)

[19]

Lee, L., Ting, H.F.: A simpler and more efficient deterministic scheme for finding frequent items over sliding windows. In: Proc. of the 25th ACM SIGACT-SIGMO D-SIGART Symposium on Principles of Database Systems, June 26-28, 2006. pp. 290–297 (2006)

[20]

Manku, G.S., Motwani, R.: Approximate frequency counts over data streams. In: Proc. of the Int. Conf. on V.L. Data Bases. VLDB (2002)

[21]

Metwally, A., Agrawal, D., Abbadi, A.E.: Efficient computation of frequent and top-k elements in data streams. In: IN ICDT (2005)

[22]

Mukherjee, B., Heberlein, L., Levitt, K.: Network intrusion detection. Network, IEEE 8 (3) (May 1994)

[23]

Sommers, J., Barford, P., Duffield, N., Ron, A.: Accurate and efficient sla compliance monitoring. In: Proc. of the Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications. SIGCOMM, ACM (2007)

[24]

Tsidon, E., Hanniel, I., Keslassy, I.: Estimators also need shared values to grow together. In: INFOCOM 2012. pp. 1889–1897

Cited By

Ben Basat REinziger GHan WTayh B(2024)SQUID: Faster Analytics via Sampled Quantile EstimationProceedings of the ACM on Networking10.1145/36768732:CoNEXT3(1-23)Online publication date: 21-Aug-2024
https://dl.acm.org/doi/10.1145/3676873
Li XLiu WLou JHong YZhang LQin ZRen K(2024)Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded MemoryProceedings of the ACM on Management of Data10.1145/36392852:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639285
Wang YWang YChen CBaeza-Yates RBonchi F(2024)DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding WindowsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671694(3255-3266)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671694
Show More Cited By

Index Terms

Heavy hitters in streams and sliding windows

Index terms have been assigned to the content through auto-classification.

Recommendations

How to catch L 2 -heavy-hitters on sliding windows

Finding heavy-elements (heavy-hitters) in streaming data is one of the central, and well-understood tasks. Despite the importance of this problem, when considering the sliding windows model of streaming (where elements eventually expire) the problem of ...
Memento: Making Sliding Windows Efficient for Heavy Hitters
Cloud operators require timely identification of Heavy Hitters (HH) and Hierarchical Heavy Hitters (HHH) for applications such as load balancing, traffic engineering, and attack mitigation. However, existing techniques are slow in detecting new heavy ...
Sliding windows over uncertain data streams

Uncertain data streams can have tuples with both value and existential uncertainty. A tuple has value uncertainty when it can assume multiple possible values. A tuple is existentially uncertain when the sum of the probabilities of its possible values is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications

2697 pages

Copyright © 2016.

Publisher

IEEE Press

Publication History

Published: 01 April 2016

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ben Basat REinziger GHan WTayh B(2024)SQUID: Faster Analytics via Sampled Quantile EstimationProceedings of the ACM on Networking10.1145/36768732:CoNEXT3(1-23)Online publication date: 21-Aug-2024
https://dl.acm.org/doi/10.1145/3676873
Li XLiu WLou JHong YZhang LQin ZRen K(2024)Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded MemoryProceedings of the ACM on Management of Data10.1145/36392852:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639285
Wang YWang YChen CBaeza-Yates RBonchi F(2024)DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding WindowsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671694(3255-3266)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671694
Yang KWu YMiao RYang TLiu ZXu ZQiu RZhao YLv HJi ZXie GSchulzrinne HKohler EMaltz DMisra V(2023)ChameleMon: Shifting Measurement Attention as Network State ChangesProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604850(881-903)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3604850
Sun HLi JHe JGui JHuang QSchulzrinne HKohler EMaltz DMisra V(2023)OmniWindow: A General and Efficient Window Mechanism Framework for Network TelemetryProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604847(867-880)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3604847
Wang FChen QLi YYang TTu YYu LCui B(2023)JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product EstimationProceedings of the ACM on Management of Data10.1145/35889351:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588935
Li YWang FYu XYang YYang KYang TMa ZCui BUhlig S(2023)LadderFilter: Filtering Infrequent Items with Small Memory and Time OverheadProceedings of the ACM on Management of Data10.1145/35886901:1(1-21)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588690
Wu YJiang SDong SZhong ZChen JHu YYang TUhlig SCui BSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)MicroscopeSketch: Accurate Sliding Estimation Using Adaptive ZoomingProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599432(2660-2671)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599432
Jie XHaoliang LWei DAo J(2022)Network Host Cardinality Estimation Based on Artificial Neural NetworkSecurity and Communication Networks10.1155/2022/12584822022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/1258482
Ye JLi LZhang WChen GShan YLi YLi WHuang J(2022)UA-Sketch: An Accurate Approach to Detect Heavy Flow based on Uninterrupted ArrivalProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545017(1-11)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545017
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents