카운트-최소 스케치

다음에 대한 시리즈 일부
확률론적 데이터 구조
블룸 필터 카운트-최소 스케치 몫필터 목록 건너뛰기
랜덤 트리
랜덤 이진 트리 트레프 빠르게 탐색되는 랜덤 트리
관련
랜덤화 알고리즘 하이퍼로그 로그
v t

컴퓨팅에서 count-min 스케치(CM sketch)는 데이터 스트림에서 사건의 빈도표 역할을 하는 확률론적 데이터 구조다.해시함수를 사용하여 이벤트를 주파수에 매핑하지만, 해시 테이블과 달리 충돌로 인한 일부 이벤트의 과대 계수를 감수하면서 하위 선형의 공간만 사용한다.count-min 스케치는 Graham Cormode와 S에 의해 2003년에 발명되었다. 무쓰 무투크리슈난이^[1] 2005년 논문에서 기술했다.^[2]

Count-min 스케치는 팬 등이 1998년에 도입한 Counting Bloom 필터와 본질적으로 동일한 데이터 구조다.^[3]그러나, 그것들은 다르게 사용되고 따라서 크기가 다르다: 카운트-민 스케치는 일반적으로 원하는 스케치의 근사 품질과 관련된 하위 선형의 셀 수를 가지고 있는 반면 카운팅 블룸 필터는 일반적으로 세트의 요소 수와 일치하도록 크기가 더 크다.

데이터 구조

count-min 스케치의 기본 버전의 목표는 이벤트 스트림을 한 번에 하나씩 소비하고 스트림에서 다양한 유형의 이벤트의 빈도를 계산하는 것이다.언제든지 이벤트 유형 $U{\displaystyle \mathcal{}}$ ${\$의 우주에서 특정 이벤트 유형 i의 주파수에 대해 스케치를 쿼리할 수 있으며, 특정 확률로 실제 주파수에서 일정 거리 내에 있는 이 주파수의 추정치를 반환한다.^[a]

실제 스케치 데이터 구조는 w열과 d행의 2차원 배열이다.스케치 w와 d 매개변수는 스케치가 작성될 때 고정되며, 빈도나 내부 제품에 대해 스케치를 쿼리할 때의 시간과 공간 필요성과 오류 확률을 결정한다.각 d 행과 연관된 해시 함수는 별도의 해시 함수로 해시 함수는 쌍으로 독립적이어야 한다.w와 d 매개변수는 w = ⌈e/ε⌉⌉ 및 d = lln 1/Δ⌉를 설정하여 선택할 수 있으며, 여기서 질의 응답의 오차는 확률 1 Δ(아래 참조), e는 오일러의 숫자다.

i 유형의 새로운 이벤트가 도착하면 다음과 같이 업데이트한다: 테이블의 각 행 j에 대해 해당 해시 함수를 적용하여 열 인덱스 k = h_j(i)를 얻으십시오.그런 다음 j행, k행의 값을 하나씩 증가시킨다.

스트림에서 몇 가지 유형의 쿼리가 가능하다.

• 가장 간단한 것은 이벤트 유형 i의 카운트를 묻는 포인트 쿼리다.추정 카운트는 ${\displaystyle i_{}}$에 대한 표의 최소값, $즉{\displaystyle {\stackrel{}{}}_{}}$ ${\displaystyle {\stackrel{}{^}}_{}}$ i${\displaystyle {}_{}}$= ${\displaystyle \underset{}{min}}$ j ${\displaystyle \underset{}{}\mathrm{}}$ ${\displaystyle \mathrm{o}}$ ${\displaystyle \mathrm{u}}$ ${\displaystyle \mathrm{t}}$[${\displaystyle j}$, h ${\displaystyle j_{}}$ (${\displaystyle {}_{}i}$)${\displaystyle }$] ${\displaystyle {\hat{a}_{i}=\min _{j}}\mathrm {count}[j,h_{j}(i$ 여기서 $c{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{o}}$ ${\displaystyle \mathrm{n}}$ ${\displaystyle \mathrm{t}}$ ${\$은 {$count}$이다$.$

분명히 각 i에 ${\displaystyle {대해}_{}}$ ${\displaystyle {\stackrel{}{^}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$가 있는데$,$ ${\displaystyle {여기}_{}}$서 i ${\$는 스트림에서 발생한 실제 주파수다.

Additionally, this estimate has the guarantee that ${\displaystyle {\hat {a}}_{i}\leq a_{i}+\varepsilon N}$ with probability ${\displaystyle 1-\delta }$, where ${\displaystyle N=\sum _{i\in {\mathcal {U}}}a_{i}}$ is the stream size, i.e. the total number of items se스케치대로

• 내부 제품 쿼리는 $c{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{o}}_{}}$ $o$ a {\$displaystyle \mathrm$ {$count}$ _$$${a}$와 c ${\displaystyle {\mathrm{o}}_{}}$ o o $o$o ${\displaystyle {}_{}}$ t {\$displaystyle \matrmatrm${count} _{$b})$의 두 개의 count min 스케치로 대표되는 히스토그램 사이에 내부 제품을 묻는다$.$

데이터 구조에 대한 작은 수정은 다른 스트림 통계를 스케치하는 데 사용될 수 있다.

백작 스케치처럼 백작-민 스케치는 선형 스케치다.즉, 두 개의 하천이 주어진 경우 각 하천에 스케치를 구성하고 스케치를 합하면 하천을 연결한 후 연결된 하천에 스케치를 구성하는 것과 동일한 결과를 얻는다.이것은 스케치를 병합할 수 있게 하고 스트리밍 설정뿐만 아니라 분산된 설정에서도 사용할 수 있게 한다.

치우침 및 오류 감소

카운트-미네 스케치에 대한 일반적인 최소 추정기의 한 가지 잠재적인 문제는 그것들이 사건의 실제 빈도에 대한 편향된 추정기라는 것이다. 즉, 그것들은 과대평가할 수 있지만, 점 질의에서는 결코 진정한 카운트를 과소평가하지 않는다.더욱이 분포가 심하게 치우쳐 있을 때는 최소 추정기가 잘 작동하지만, 분포가 충분히 치우치지 않을 때는 수단에 기초한 카운트 스케치와 같은 다른 스케치가 더 정확하다.오차를 줄이고 편향을 줄이거나 제거하기 위해 스케치의 몇 가지 변형이 제안되었다.^[4]

치우침을 제거하기 위해 hCount* 추정기는 스케치에서 d 랜덤 항목을 반복적으로 선택하고 최소값을 취하여 치우침의 불편 추정치를 구한 후 이를 뺀다.

최대우도 추정기(MLE)는 Ting에서 도출되었다.^[6]MLE를 사용함으로써 추정기는 항상 최소 추정기와 일치하거나 더 잘 조합할 수 있으며 분포가 치우치지 않더라도 잘 작동한다.또한 본 논문에서는 hCount* debiasing 작업이 무작위 샘플링 없이 효율적으로 계산될 수 있는 부트스트래핑 절차라는 것을 보여주었으며, 어떤 추정기로도 일반화할 수 있다.

우주의 미지의 아이템과 해시 충돌에서 오류가 발생하기 때문에 우주의 여러 원소가 동시에 알려져 있거나 쿼리될 때 충돌에 대해 여러 가지 접근법이 수정된다.^[8][6]이들 각각의 경우에, 우주의 많은 부분이 유의미한 이익을 관찰하기 위해 알려져 있어야 한다.

보수적인 업데이트는 업데이트를 변경하지만 쿼리 알고리즘은 변경하지 않는다.To count c instances of event type i, one first computes an estimate ${\displaystyle {\hat {a}}_{i}=\min _{j}\mathrm {count} [j,h_{j}(i)]}$, then updates ${\displaystyle \mathr$$m {count} [j,h_{j}(i)]\왼쪽$ 화살표 $\max\{\\mathrm {count}[j,h_{j}(i)],$ {\$hat {a_{i}}}+c\}}}$ 각 행에 대해.이 업데이트 절차는 스케치를 선형 스케치가 아니지만, 여전히 병합할 수 있다.

참고 항목

• 피쳐 해싱
• 지역감응 해싱
• 민해시
• 스케치 카운트

메모들

참조

추가 읽기

• Dwork, Cynthia; Naor, Moni; Pitassi, Toniann; Rothblum, Guy N.; Yekhanin, Sergey (2010). Pan-private streaming algorithms. Proc. ICS. CiteSeerX 10.1.1.165.5923.
• Schechter, Stuart; Herley, Cormac; Mitzenmacher, Michael (2010). Popularity is everything: A new approach to protecting passwords from statistical-guessing attacks. USENIX Workshop on Hot Topics in Security. CiteSeerX 10.1.1.170.9356.

외부 링크

• 카운트-최소 FAQ