Count-Min HyperLogLog : 네트워크 빅데이터를 위한 카디널리티 추정 알고리즘

Vol. 33, No. 3, pp. 427-435, 6월. 2023
10.13089/JKIISC.2023.33.3.427, Full Text:
Keywords: Big Network Data, Cardinality Estimation, Sketch
Abstract

카디널리티 추정은 실생활의 많은 곳에서 사용되며, 큰 범위의 데이터를 처리하는 데 근본적 문제이다. 인터넷이 빅데이터의 시대로 넘어가며 데이터의 크기는 점점 커지고 있지만, 작은 온칩 캐시 메모리만을 이용하여 카디널리티 추정이 이뤄진다. 메모리를 효율적으로 사용하기 위해서, 지금까지 많은 방법이 제안되었다. 그러나, 이러한 알고리즘에서는 estimator 간의 노이즈 발생으로 인해 정확도가 떨어지는 일이 발생한다. 이 논문에서는 노이즈를 최소화하는데 중점을 뒀다. 우리는 여러 개의 데이터 구조를 제안하여 각 estimator가 데이터 구조 수만큼의 추정값을 가지고, 이 중 가장 작은 값을 선택하여 노이즈를 최소화한다. 실험을 통해 이 방법이 이전의 가장 좋은 방법과 비교했을 때, 플로우당 1 bit와 같은 작은 메모리를 사용하면서 더 좋은 성능을 보이는 것을 확인했다.

Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
강신정 and 양대헌, "Count-Min HyperLogLog : Cardinality Estimation Algorithm for Big Network Data," Journal of The Korea Institute of Information Security and Cryptology, vol. 33, no. 3, pp. 427-435, 2023. DOI: 10.13089/JKIISC.2023.33.3.427.

[ACM Style]
강신정 and 양대헌. 2023. Count-Min HyperLogLog : Cardinality Estimation Algorithm for Big Network Data. Journal of The Korea Institute of Information Security and Cryptology, 33, 3, (2023), 427-435. DOI: 10.13089/JKIISC.2023.33.3.427.