근사 계수 알고리즘

Approximate counting algorithm

대략적인 카운팅 알고리즘은 소량의 메모리를 사용하여 많은 수의 이벤트를 카운트할 수 있다.1977년 벨 연구소의 로버트 모리스(크립토그래퍼)에 의해 발명된 것으로, 확률론적 기법을 사용하여 카운터를 증분한다.1980년대 초 근사치라는 이름을 만든 INRIA Rocquencourt의 필리프 플라호레(Philipe Flajolet)에 의해 충분히 분석되어 연구계의 인정에 크게 기여하였다.높은 품질의 근사치와 낮은 고장 확률에 초점을 맞추었을 때, 넬슨과 유는 모리스 카운터를 아주 약간 수정하는 것이 문제의 모든 알고리즘 중에서 점증적으로 최적이라는 것을 보여주었다.[1]알고리즘은 스트리밍 알고리즘의 전구 중 하나로 간주되며, 데이터 스트림의 주파수 모멘트를 결정하는 보다 일반적인 문제가 필드의 중심이 되었다.

운영이론

모리스 알고리즘을 사용하여 카운터는 실제 카운트의 "크기 추정 순서"를 나타낸다.그 근사치는 수학적으로 편견이 없다.

카운터를 증가시키기 위해 의사 난수 이벤트를 사용하며, 따라서 증가는 확률론적 사건이다.공간을 절약하기 위해 지수만 유지된다.예를 들어, 베이스 2에서 카운터는 카운트를 1, 2, 4, 8, 16, 32로 추정할 수 있으며, 2의 모든 힘을 추정할 수 있다.메모리 요건은 단순히 지수를 고정하는 것이다.

예를 들어, 4에서 8로 증가하기 위해서는 0.25의 확률로 카운터에 양의 변화를 발생시키는 의사 난수가 생성될 것이다.그렇지 않으면 카운터는 4에 머물러 있다.

아래 표는 카운터의 일부 잠재적 값을 보여준다.

카운터의 저장된 이진수 값 근사치 실제 카운트에 사용할 수 있는 값의 범위 기대치(충분히 큰 n, 균일한 분포)
0 1 0 또는 초기 값 0
1 2 1개 이상 2
10 4 2개 이상 6
11 8 3개 이상 14
100 16 4개 이상 30
101 32 5개 이상 62

카운터가 지수 5(십진수 등가 101)와 같은 101의 값을 갖는 경우, 추정 카운트는 2^5 또는 32이다.There is a fairly low probability that the actual count of increment events was 5 ().증분 사건의 실제 카운트는 "약 32"가 될 가능성이 높지만 임의로 높을 수 있다(실제 카운트의 확률이 39보다 높을 경우).

카운터 값 선택

카운터 값으로 2의 파워를 사용하는 것이 메모리 효율적이지만 임의의 값은 동적 오류 범위를 만드는 경향이 있으며, 값이 작을수록 큰 값보다 큰 오류 비율을 갖는다.카운터 값을 선택하는 다른 방법에서는 최적의 값 집합을 제공하기 위해 메모리 가용성, 원하는 오류 비율 또는 카운팅 범위와 같은 파라미터를 고려한다.[2]

그러나 여러 카운터가 동일한 값을 공유하면 카운트 범위가 가장 큰 카운터에 따라 값이 최적화되며, 작은 카운터에 대해서는 최적 이하의 정확도를 산출한다.완화는 독립 카운터 추정 버킷을 유지 관리함으로써 달성되며,[3] 버킷의 다른 카운터에 대한 더 큰 카운터의 영향을 제한한다.

알고리즘.

카운터를 증가시킬 때, 카운터의 현재 값의 횟수를 "동전 플립"한다.매번 "Heads"가 나타나면 카운터를 증가시킨다.그렇지 않으면 증분하지 마십시오.

이는 "c" 사이비 무작위 비트(여기서 "c"는 카운터의 현재 값)를 생성하고 모든 비트에 논리적 AND 기능을 사용하여 프로그래밍 방식으로 수행할 수 있다.이러한 의사 난수 비트 중 하나가 0이면 0이고, 모두 0이면 1이 된다.계산대에 결과를 추가하기만 하면 된다.이 절차는 카운터를 증가시키기 위한 요청이 있을 때마다 실행된다.

적용들

알고리즘은 대형 데이터 스트림을 검사할 때 유용하다.이것은 특히 데이터 압축, 시력 및 음향 인식, 기타 인공지능 애플리케이션에 유용하다.

참고 항목

참조

  1. ^ Nelson, Jelani; Yu, Huacheng (2020). "Optimal bounds for approximate counting". arXiv:2010.02116. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  2. ^ 싯돈, 에레스, 이도 한니엘, 아이작 케슬래시."추정자는 함께 성장하기 위해 공유된 가치도 필요하다." INFOCOM, 2012 Procedures IEEE.IEEE, 2012.
  3. ^ Einziger, G.; Fellman, B.; Kassner, Y. (April 2015). "Independent counter estimation buckets". 2015 IEEE Conference on Computer Communications (INFOCOM): 2560–2568. doi:10.1109/INFOCOM.2015.7218646. ISBN 978-1-4799-8381-0.

원천

  • 모리스, R. 작은 레지스터에서 많은 사건 수를 세고 있다.ACM 21, 10(1978), 840–842의 통신
  • Flajolet, P. 대략적인 계산: 상세 분석.BIT 25, (1985), 113–134 [1]
  • Michael F, Chung-Kuei L, Prodinger, Poisson-Laplace-Mellin 방법을 통한 근사 계산 [2]