계수형 간결성 문제

컴퓨터 과학에서 계수형 간결성 문제^[1](응용수학에서도 카디널리티 추정 문제로 알려져 있음)는 반복되는 원소가 있는 데이터 스트림에서 구별되는 원소의 수를 찾는 문제다.이것은 수많은 어플리케이션에서 잘 알려진 문제다.요소는 라우터를 통과하는 패킷의 IP 주소, 웹 사이트의 고유한 방문자, 대형 데이터베이스의 요소, DNA 시퀀스의 모티브 또는 RFID/센서 네트워크의 요소를 나타낼 수 있다.

형식 정의

인스턴스:A stream of elements ${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$ with repetitions, and an integer ${\displaystyle m}$. Let ${\displaystyle n}$ be the number of distinct elements, namely ${\displaystyle n= \left\{{x_{1},x_{2},\ldots ,x_{s}$$}\right\}$$}$ 그리고 이 요소들을${\displaystyle }${${\displaystyle {e\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle {}_{}}$e ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle }$…,${\displaystyle }$e ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\$\{$e_{1},$e_{$2},\ldots,$ e_{$n}\n$}\right$\}}$이 되도록 하십시오$.$

목표:$m{\displaystyle }$ ${\displaystyle m}$ 저장$$ 단위만 사용하여$$ n ${\displaystyle n}$의 추정치 $n{\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ ${\displaystyle {n}$을(를) 찾으십시오($여기$서 m${\displaystyle \mathrm{nn}}${\$displaystyle$ m$\ll$ n$\}).$

카디널리티 추정 문제의 예로는 스트림: $a{\displaystyle ,}$ ${\displaystyle b,}$ ${\displaystyle a,}$ ${\displaystyle c,}$ ${\displaystyle d,}$ ${\displaystyle d,}$ ${\displaystyle d}$, d ${\displaystyle a,b,a,c,$${\displaystyle d}$$,d},$d$\}.$ 이${\displaystyle }예$에서는$$= {${\displaystyle a}$,b,c${\displaystyle ,d}$},${\displaystyle \mathrm{d}\}}$ = 4 {\$displaysty$ n=$\{a,b,c,d}\}$ =$4$

순진한 해결책

그 문제에 대한 순진한 해결책은 다음과 같다.

카운터, c, to 0, $c{\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle 0}$을 초기화한다. c ← 0 ${\displaystyle c\leftarrow$ 0$\}.$ 삽입과 멤버십을 빠르게 수행할 수 있는 해시 테이블이나 검색 트리 등 효율적인 사전 데이터 구조 D를 초기화한다.각 요소 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$에 대해 구성원 자격 조회가 발행된다$.$If ${\displaystyle x_{i}}$ is not a member of D (${\displaystyle x_{i}\notin D}$) Add ${\displaystyle x_{i}}$ to D          Increase c by one, ${\displaystyle c\leftarrow c+1}$      Otherwise (${\displaystyle x_{i}\in D}$) do nothing.출력 $n{\displaystyle }$= ${\displaystyle c}$ ${\displaystyle n=c}$.

구별되는 원소의 수가 너무 많지 않은 한, D는 메인 메모리에 들어맞고 정확한 답을 검색할 수 있다.그러나 이 접근방식은 경계 저장소에 대해 확장되지 않으며, 각 요소 x ${\displaystyle i_{}}$ ${\$에 대해 수행된 계산을 최소화해야 하는$$ 경우.이 경우, 정해진 수의 저장 단위를 사용하는 여러 스트리밍 알고리즘이 제안되었다.

HyperLog 알고리즘

스트리밍 알고리즘

경계 스토리지 제약 조건을 처리하기 위해 스트리밍 알고리즘은 무작위화를 사용하여 고유한 수의 요소($n{\displaystyle }$ ${\displaystyle n$에 대한 비정확한 추정을 생성한다$.$ 최첨단 추정기는 해시함수 $h{\displaystyle }$ (${\displaystyle }$e $){\displaystyle$ $e_{j}$ 모든 요소를 해시함수를 사용하여 저차원 데이터 스케치로$$ 해시한다.$Playstyle h(e_{j$서로 다른 기법은 그들이 저장하는 데이터 스케치에 따라 분류될 수 있다.

최소/최대 스케치

최소/최대 스케치는^[2][3] 최소/최대 해시 값만 저장한다.알려진 최소/최대 스케치 추정기의 예:Chassaing 등에서는 문제에 대한 최소-분산 불편 추정기인 최대 스케치를 제시한다.연속적인 최대 스케치 추정기는 최대우도 추정기다.실제로 선택한 추정기는 HyperLog 알고리즘이다.^[6]

그러한 추정자 뒤에 있는 직관은 각각의 스케치가 원하는 수량에 대한 정보를 담고 있다는 것이다.For example, when every element ${\displaystyle e_{j}}$ is associated with a uniform RV, ${\displaystyle h(e_{j})\sim U(0,1)}$, the expected minimum value of ${\displaystyle h(e_{1}),h(e_{2}),\ldots ,h(e_{n})}$ is ${\display$$스타일$ 1$/(n+1)}$.$해시함수$는 e${\displaystyle }$${\displaystyle j_{}}$ ${\displaystyle h(e_{j}})$가 e j ${\$의 모든 모양에 대해 동일함을$$ 보장한다$.$따라서 중복의 존재는 극단적 순서 통계의 가치에 영향을 미치지 않는다.

최소/최대 스케치 외에 다른 추정 기법이 있다.Flajolet 외 에 의한 계수-간결한 추정에 관한 첫 번째 논문은 비트 패턴 스케치를 설명한다^[7].이 경우 원소는 비트 벡터로 해시되며 스케치는 모든 해시 값의 논리적 OR을 보유한다.이 문제에 대한 최초의 무증상-공간적-시간적-최적 알고리즘은 다니엘 M. 케인, 젤라니 넬슨, 데이비드 P에 의해 주어졌다.우드러프.^[8]

맨 아래-m 스케치

Bottom-m 스케치는 $최소값$인$$m {\$displaystyle$ m} 최소값을 유지하는 최소 스케치의 $일반화$로서${\displaystyle ,}$ 여기서 ${\displaystyle \mathrm{m}}$ $\$ 1 {\$displaystyle$ m\geq $1}$을(를$)$ 참조한다$.$ count-distick 추정 알고리즘의 이론적 개요는 Cosma et al.^[2]을 참조하고, 비교 시뮬레이션 결과를 통한 실제 개요는^[10] Metwally를 참조한다.

가중 카운트-간결함 문제

가중치 버전에서 각 요소는 가중치와 연관되며 목표는 가중치의 총 합계를 추정하는 것이다.형식적으로.

인스턴스:A stream of weighted elements ${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$ with repetitions, and an integer ${\displaystyle m}$. Let ${\displaystyle n}$ be the number of distinct elements, namely ${\displaystyle n= \left\{{x_{1},x_{2},\ldo$$ts ,x_{s}}\right$ 이 요소들을${\displaystyle }${${\displaystyle e{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$e ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ ${\$$j$$\}\}\}.$ ${\displaystyle {마지막}_{}}$으로 w j$${\$displaystystyle w_{j$$}$을 $}$의 무게로 한다$$$.$

목표:$m{\displaystyle }$ ${\$$displaystyle$ m$\$$widehat$${w}$의${\displaystyle }$w${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ j${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{\mathrm{1n}}}}$ ${\displaystyle j_{}}$ ${\$ w$=\sum _{j=1}^{n1}w_{j}}}}}$의 $추정치$를 찾으십시오. $여기$서 m$\$ {\$displaystystyle m\ll$ n$\}.$

An example of an instance for the weighted problem is: ${\displaystyle a(3),b(4),a(3),c(2),d(3),b(4),d(3)}$. For this instance, ${\displaystyle e_{1}=a,e_{2}=b,e_{3}=c,e_{4}=d}$, the weights are ${\displaystyle w_1=3,w_{}}$${\displaystyle 2_{}}$= ${\displaystyle 4}$,${\displaystyle {w\mathrm{}}_{}}$ 3${\displaystyle {}_{}}$= ${\displaystyle 2}$,${\displaystyle {}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$= ${\displaystyle 3}$ ${\displaystyle w_{1}=3,w_{2}=4,w_{3}=2,w_{4}=3$$},$${\displaystyle }$∑ ${\displaystyle w_{}}$= ${\displaystyle 12}$ ${\displaystyle \sum$ {w_${j}}=12$

애플리케이션 예로서, ${\displaystyle {x\mathrm{}}_{}}$1, ${\displaystyle {x\mathrm{}}_{}}$ 2${\displaystyle }$,${\displaystyle x_{}}$ ${\displaystyle {}_{}}$ ${\$는 서버가 수신한 IP 패킷일 수 있다$$.각 패킷은 $n{\displaystyle }$ ${\displaystyle n}$ IP$$ 흐름 $e{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$e ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ e ${\displaystyle n_{}}$ ${\$ 중 하나에 속한다$.$${\displaystyle w_{}}$ j ${\$ 중량은 서버의$$ ${\displaystyle {flow}_{}}$ $e{\displaystyle {}_{}}$ j ${\$에 의해 부과되는 부하일 수 있다$$.따라서 $\sum {\displaystyle \underset{j}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle j_{}}$ ${\$는 $패킷{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}{}_{}}$, x${\displaystyle {}_{}{2\mathrm{}}_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle s_{}}${\$displaystyle x_{1},\dots ,x_{s}}}$이 속하는 모든 흐름에 의해 서버에 부과되는 총 부하를 나타낸다$$.

가중 카운트-간결함 문제 해결

가중치 없는 문제에 대한 모든 극단적 순서 통계 추정기(최소/최대 스케치)는 가중된 문제에 대한 추정기로 일반화할 수 있다.^[11]예를 들어 Cohen 등이 제안한 가중 추정기는 가중 문제를 해결하기 위해 연속적인 최대 스케치 추정기를 확장했을 때 얻을 수 있다.^[5]특히 HyperLog 알고리즘을 확장해 가중 문제를 해결할 수 있다.확장된 HyperLog 알고리즘은 가중 문제에 대해 알려진 다른 모든 알고리즘 중에서 통계 정확도와 메모리 사용 측면에서 최고의 성능을 제공한다.

참고 항목

• 카운트-최소 스케치
• 스트리밍 알고리즘
• 최대우도
• 최소-분산 불편 추정기

참조