Effect of Sampling for Multi-set Cardinality Estimation
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Estimating the number of distinct values is really well-known problems in network data measurement and many effective algorithmsare suggested. Recent works have built upon technique called Linear Counting to solve the estimation problem for massive sets orspreaders in small memory. Sampling is used to reduce the measurement data, and it is assumed that sampling gives bad effect on theaccuracy. In this paper, however, we show that the sampling on multi-set estimation sometimes gives better results for CSE withsampling than for MCSE that examines all the packets without sampling in terms of accuracy and estimation range. To prove this, wepresented mathematical analysis, conducted experiment with real data, and compared the results of CSE, MCSE, and CSES.
Abstract
Estimating the number of distinct values is really well-known problems in network data measurement and many effective algorithmsare suggested. Recent works have built upon technique called Linear Counting to solve the estimation problem for massive sets orspreaders in small memory. Sampling is used to reduce the measurement data, and it is assumed that sampling gives bad effect on theaccuracy. In this paper, however, we show that the sampling on multi-set estimation sometimes gives better results for CSE withsampling than for MCSE that examines all the packets without sampling in terms of accuracy and estimation range. To prove this, wepresented mathematical analysis, conducted experiment with real data, and compared the results of CSE, MCSE, and CSES.
참고문헌 (13)
- Counting distinct elements in a data stream, "Z. Bar-Yossef", Randomization and Approximation Techniques in Computer Science, 1~10 (2002)
- A. Chen, "Distinct counting with a self-learning bitmap", Journal of the American Statistical Association, 1171(1174) (2011)
- P. Flajolet, "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm", DMTCS Proceedings (2008)
- P. Flajolet, "Probabilistic counting algorithms for data base applications", Journal of Computer and System Sciences, pp.182~209 (1985)
- D. Kane, "An optimal algorithm for the distinct elements problem", Proceedings of the twenty-ninth ACM, pp.41~52 (2010)
- J. Cao, "Identifying high cardinality internet hosts", INFOCOM 2009, pp.810~818 (2009), IEEE
- C. Estan, "pp. 925-937", Proceedings of the 3rd ACM SIGCOMM, pp.925~937 (2003)
- X. Shi, "An online framework for catching top spreaders and scanners", Computer Networks, pp.1375~1388 (2010)
- Q. Zhao, "Detection of Super Sources and Destinations in High-Speed Networks: Algorithms, Analysis and Evaluation", IEEE Journal on Selected Areas in Communications, pp.1840~1852 (2006)
- M. Yoon, "Fit a spread estimator in small memory", INFOCOM 2009 (2009), IEEE
- T. Li, "Spreader classification based on optimal dynamic bit sharing", Networking, IEEE, 2013, 817~830
- K. -Y. Whang, "A linear-time probabilistic counting algorithm for database applications", ACM Transactions on Database Systems, pp.208~229 (1990)
- B. Choi, "Observations on cisco sampled net flow", ACM SIGMETRICS Performance Evaluation, pp.18~23 (2005)