Count-Min HyperLogLog : 네트워크 빅데이터를 위한 카디널리티 추정 알고리즘
Count-Min HyperLogLog : Cardinality Estimation Algorithm for Big Network Data
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
카디널리티 추정은 실생활의 많은 곳에서 사용되며, 큰 범위의 데이터를 처리하는 데 근본적 문제이다. 인터넷이 빅데이터의 시대로 넘어가며 데이터의 크기는 점점 커지고 있지만, 작은 온칩 캐시 메모리만을 이용하여 카디널리티 추정이 이뤄진다. 메모리를 효율적으로 사용하기 위해서, 지금까지 많은 방법이 제안되었다. 그러나, 이러한 알고리즘에서는 estimator 간의 노이즈 발생으로 인해 정확도가 떨어지는 일이 발생한다. 이 논문에서는 노이즈를 최소화하는데 중점을 뒀다. 우리는 여러 개의 데이터 구조를 제안하여 각 estimator가 데이터 구조 수만큼의 추정값을 가지고, 이 중 가장 작은 값을 선택하여 노이즈를 최소화한다. 실험을 통해 이 방법이 이전의 가장 좋은 방법과 비교했을 때, 플로우당 1 bit와 같은 작은 메모리를 사용하면서 더 좋은 성능을 보이는 것을 확인했다.
Abstract
Cardinality estimation is used in wide range of applications and a fundamental problem processing a large range of data. While the internet moves into the era of big data, the function addressing cardinality estimation use only on-chip cache memory. To use memory efficiently, there have been various methods proposed. However, because of the noises between estimator, which is data structure per flow, loss of accuracy occurs in these algorithms. In this paper, we focus on minimizing noises. We propose multiple data structure that each estimator has the number of estimated value as many as the number of structures and choose the minimum value, which is one with minimum noises, We discover that the proposed algorithm achieves better performance than the best existing work using the same tight memory, such as 1 bit per flow, through experiment.
참고문헌 (20)
- "Researchers transmit optical data at 16.4 Tbps"[URL]
- C. Estan, "Bitmap algorithms for counting active flows on high-speed links", Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, pp.153~166 (2003)
- Z. Bar-yossef, "Counting distinct elements in a data stream", Lecture Notes in Computer Science, RANDOM 2002, LNCS, 2483, pp.1~10 (2002)
- C. Estan, "New directions in traffic measurement and accounting", Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, pp.323~336 (2002)
- M. Durand, "Loglog counting of large cardinalities", ESA: European Symposia on Algorithms, LNCS, 2832, pp.605~617 (2003)
- P. Lieven, "High-speed per-flow traffic measurement with probabilistic multiplicity counting", Proc. of IEEE INFOCOM, pp.1~9 (2010)
- Q. Xiao, "Hyper-compact virtual estimators for big network data based on register sharing", Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp.417~428 (2015)
- K. -Y. Whang, "A linear-time probabilistic counting algorithm for database applications", ACM Transactions on Database Systems, 15(2), pp.208~229 (1990)
- "dataset:passive_2013_pcap"[URL]
- S. Heule, "HyperLogLog in practice : Algorithmic engineering of a state-of-the-art cardinality estimation algorithm", Proceedings of the 16th International Conference on Extending Database Technology, pp.683~692 (2013)
- P. Flajolet, "Probabilistic counting algorithms for database applications", Journal of computer and system sciences, 31(2), pp.182~209 (1985)
- M. Yoon, "Fit a spread estimator in small memory", IEEE INFOCOM 2009, pp.504~512 (2009)
- P. Flajolet, "HyperLogLog : The analysis of a near-optimal cardinality estimation algorithm", Proc. of AOFA: International Conference on Analysis Of Algorithms, pp.137~156 (2007)
- Q. Zhao, "Detection of super sources and destinations in high-speed networks : Algorithms, analysis and evaluation", IEEE Journal on Selected Areas in Communications, 24(10), pp.1840~1852 (2006)
- Q. Xiao, "Estimating the persistent spreads in high-speed networks", 2014 IEEE 22nd International Conference on Network Protocols, pp.131~142 (2014)
- Q. Xiao, "Differential estimation in dynamic RFID systems", Proceedings IEEE INFOCOM, pp.295~299 (2013)
- M. Costa, "Vigilante : End-to-end containment of internet worms", Proceedings of the twentieth ACM symposium on Operating systems principles, 39(5), pp.133~147 (2005)
- C. C. Zou, "Monitoring and early warning for internet worms", Proceedings of the 10th ACM conference on Computer and communications security, pp.190~199 (2003)
- Dinh Nguyen Dao, "Minimizing Noise in HyperLogLog-Based Spread Estimation of Multiple Flows", 2022 52nd Annual IEEE, 2022, 331~342
- G. Cormode, "An improved data stream summary : the count-min sketch and its applications", Journal of Algorithms, 55(1), pp.58~75 (2005)