스트리밍 알고리즘

컴퓨터 과학에서 스트리밍 알고리즘은 입력이 항목 순서에 따라 제시되는 데이터 스트림을 처리하기 위한 알고리즘으로, 몇 번의 패스(일반적으로 단 한 번의 패스)만으로 검사할 수 있다.대부분의 모델에서 이러한 알고리즘은 제한된 메모리(일반적으로 스트림의 최대값 및/또는 크기의 로그)에 접근할 수 있다.또한 품목당 처리 시간이 제한될 수 있다.null

이러한 제약조건은 알고리즘이 데이터 스트림의 요약이나 "스케치"에 근거한 근사적인 답변을 생성하는 것을 의미할 수 있다.null

역사

스트리밍 알고리즘은 이미 문로와 패터슨에^[1] 의해 1978년 초에 연구되었고, 필립 플라졸레와 G도 연구되었다.니겔 마틴은 1982/83년에 스트리밍 알고리즘 분야가 노가 알론, 요시 마티아스, 마리오 스제지에 의해 1996년 논문에서 처음으로 공식화되고 대중화되었다.^[2][3]이 논문의 경우, 저자들은 이후 2005년 괴델상을 "스트리밍 알고리즘에 대한 기초적 공헌"으로 수상했다.그 후 이론, 데이터베이스, 네트워킹, 자연어 처리 등 다양한 컴퓨터 과학 분야에 걸쳐 있는 데이터 스트리밍 알고리즘을 중심으로 한 대규모 작업이 이루어졌다.null

반스트리밍 알고리즘은 허용된 공간이 정점 수에서 선형인 ^[4]그래프의 스트리밍 알고리즘의 완화로 2005년에 도입되었다.n, 그러나 가장자리 수의 로그만m. 이러한 이완은 조밀한 그래프에 여전히 의미가 있으며,${\displaystyle }o{\displaystyle }$ (${\displaystyle n}$) ${\displaystyle o (n)}$ 공간에서$$ 풀 수 없는 흥미로운 문제(연결성 등)를 해결할 수 있다.null

모델

데이터 스트림 모델

데이터 스트림 모델에서, 입력의 일부 또는 전부는 (일부 유한 도메인에서) 한정된 정수 시퀀스로 표현되며, 일반적으로 무작위 액세스는 가능하지 않지만, 대신 "스트림"^[5]에서 한 번에 하나씩 도착한다.스트림의 길이가 있는 경우n도메인의 크기는m, 알고리즘은 일반적으로 로그가 있는 공간을 사용하도록 제한된다.m그리고n그들은 일반적으로 개울 위를 지나가는 횟수의 적은 수의 패스만 할 수 있고, 때로는 한 번 패스만 할 수 있다.^[6]

개찰구 및 현금 레지스터 모델

스트리밍 문헌의 대부분은 저장하기에 너무 큰 주파수 분포에 대한 계산 통계와 관련이 있다.이 ${\displaystyle {}_{}}$의 문제의 경우 스트림에서 이를 업데이트한 $벡터{\displaystyle \mathbf{}}$a ${\displaystyle =}$ ( ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle n_{}}$) ${\displaystyle \mathbf$ {a$}$= ($a_{1},\dots,a_n})$가 있다($$영점 $벡터{\displaystyle \mathbf{}}$ 0 ${\$이러한 알고리즘의 목표는 ${\$의$$함수를 ${\$를) 정확하게$$ 나타내는 데 필요한 공간보다 상당히 적은 공간을 사용하여$$ $계산$하는 것이다.이러한 스트림을 업데이트하기 위한 두 가지 일반적인 모델이 있는데, "현금 레지스터"와 "턴스틸" 모델이다.^[7]null

현금 레지스터 모델에서 각 업데이트는 update${\displaystyle i,}$ ${\displaystyle c}$ ${\displaystyle ⟩}$ ${\displaystyle \langle$ i$,c\rangele$ $\}$ 형식으로 되어 있어 ${\displaystyle i_{}}$ ${\$가 일부 양의 정수 $c{\displaystyle }$ ${\displaystystyle$ c$}만큼$ 증가된다$.$ $주목$할 만한${\displaystyle \mathrm{특별}}$한 경우는$$c = 1 {\$displaysty$ c=1$}($단위만 허용).null

In the turnstile model, each update is of the form ${\displaystyle \langle i,c\rangle }$, so that ${\displaystyle a_{i}}$ is incremented by some (possibly negative) integer ${\displaystyle c}$. In the "strict turnstile" model, no ${\displaystyle a_{i}}$ at any time may be less than zero.null

슬라이딩 윈도우 모델

몇몇 논문들은 또한 "슬라이딩 윈도우" 모델을 고려한다.^{[citation needed]}이 모델에서 관심의 기능은 스트림의 고정 크기 창 위에 컴퓨팅을 하는 것이다.하천이 진행됨에 따라 창구 끝부분의 항목들은 고려 대상에서 제외되고 하천에서 새 항목들이 그 자리를 대신하게 된다.null

위의 빈도에 근거한 문제 외에도, 몇몇 다른 유형의 문제들도 연구되었다.많은 그래프 문제는 인접 행렬 또는 인접 리스트가 알 수 없는 순서로 스트리밍되는 설정에서 해결된다.또한 하천 내 역행 횟수를 세고 가장 오래 증가하는 역순을 찾는 등 하천 순서에 매우 의존하는 문제(즉, 비대칭 기능)도 있다.^{[citation needed]}null

평가하기

이 절은 출처를 인용하지 않는다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션을 개선할 수 있도록 도와주십시오. 비소싱 소재에 이의를 제기하여 제거할 수 있음(2021년 4월) (이 템플릿 메시지 제거 방법 및 시기 학습)

데이터 스트림에서 작동하는 알고리즘의 성능은 다음 세 가지 기본 요소에 의해 측정된다.

• 알고리즘이 스트림을 통과해야 하는 패스 수입니다.
• 사용 가능한 메모리.
• 알고리즘의 실행 시간.

이들 알고리즘은 모두 모든 데이터를 이용할 수 있기 전에 결정을 내려야 하지만 동일하지 않기 때문에 온라인 알고리즘과 유사한 점이 동일하지는 않다.데이터 스트림 알고리즘은 사용 가능한 메모리가 제한되어 있지만, 지점 그룹이 도착할 때까지 동작을 연기할 수 있는 반면, 온라인 알고리즘은 각 지점이 도착하는 즉시 조치를 취해야 한다.null

알고리즘이 근사 알고리즘이라면 답의 정확도는 또 다른 핵심 요인이다.정확도는 알고리즘이 확률 $1{\displaystyle \mathrm{}\Delta }$ {\$displaystyle \epsilon$ $,\delta$$}$보다 작은 $오류$를 달성한다는 근사치를$$ 의미하는 (${\displaystyle }$$\{,$ 확률 1 Δ ${\displaystyle 1-\delta }.$

적용들

스트리밍 알고리즘은 코끼리 흐름에 대한 네트워크 링크 모니터링, 고유 흐름의 수 계산, 흐름 크기의 분포 추정 등 네트워킹에 여러 응용 프로그램을 가지고 있다.^[8]그들은 또한 조인^{[citation needed]} 크기를 추정하는 것과 같은 데이터베이스에 응용프로그램을 가지고 있다.null

일부 스트리밍 문제

빈도 모멘트

${\${${\displaystyle a\mathbf{}}$$}}$ $주파수{\displaystyle \mathbf{}}$ 집합의 k번째 주파수 모멘트는 $F$ ${\displaystyle k_{}}$( a${\displaystyle }$) =${\displaystyle \underset{}{\overset{}{}}}$ i${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle a_{}^{}}$ i ${\displaystyle {}_{}^{}}$ ${\$로 정의된다$.$

첫 번째 순간 $F{\displaystyle {}_{}}$ ${\$}는 단순히 주파수의 합계(즉, 총 카운트)이다$$.두 번째 모멘트 $F{\displaystyle {}_{}}$ ${\$}}번은 지니 변동 계수 등 데이터의 통계적 특성을 계산하는 데 유용하다$$.$∞{\$는 가장 빈번한 항목의 빈도로 정의된다$$.null

알론, 마티아스, 세제디의 세미날 논문은 빈도 모멘트를 추정하는 문제를 다루었다.^{[citation needed]}null

빈도 모멘트 계산

주파수 모멘트를 찾기 위한 직접적인 접근은 order (1${\displaystyle ,}$2,3,4,...,N)의_i 모든 개별 요소에 대해 레지스터 m을_i 유지할 것을 요구한다. $\Omega {\displaystyle \mathrm{}}$ (${\displaystyle N}$) ${\displaystyle \Oomega (N)}$의 최소 메모리가 필요하다$.$^[3] 그러나 우리는 공간 제한이 있고 훨씬 더 낮은 메모리에서 계산하는 알고리즘이 필요하다.이것은 정확한 값 대신 근사를 사용하여 얻을 수 있다.F의_k 근사치를 계산하는 알고리즘으로, 여기서 F'_k는_k F의 근사치 값이다.^[9]여기서 ε은 근사 모수, Δ는 신뢰 모수다.^[10]null

F₀(DataStream의 간결한 요소) 계산

FM-스케치 알고리즘

Flajolet 등은 로버트 모리스의 논문에서 영감을 얻은 확률론적 셈법을 도입했다.^[11]모리스는 논문에서 정확성 요건을 떨어뜨리면 카운터 n을 로그 n 비트에 저장할 수 있는 카운터 로그 n으로 대체할 수 있다고 말한다.^[12]Flajolet 등은 해시공간(길이 L의 이진 문자열)에서 원소를 균일하게 분포한다고 가정하는 해시함수 h를 사용하여 이 방법을 개선했다.null

${\displaystyle h:[m]\오른쪽 화살표 [0,2^{L}-1]}$

비트(y,k)는 k번째 비트를 y의 이진법으로 나타냄

${\displaystyle y=\sum _{k\geq 0}\mathrm {bit}(y,k)*2^{k}}$

let $\rho {\displaystyle }$( ${\displaystyle y}$) ${\displaystyle \rho (y)}$은(는) $\rho {\displaystyle }$( 0${\displaystyle }$) ${\displaystyle \rho (0)}$에 적합한 규칙과 함께 y의_i 이진 표현에서 최하위 1비트의 위치를$$ 나타낸다$.$

${\displaystyle \rho(y)={\begin{case}\mathrm {Min}(k:\mathrm {bit}(y,k)=1)&{\text{}}}}}}}}}}}}.L&{\text{{}if }y=0\end{case}}$

A를 카디널리티를 결정해야 하는 길이 M의 데이터 스트림의 순서가 되도록 한다.비트맵으로 설정 [0...L - 1]가 되다

ρ(해시값)이 기록되는 해시 공간.그 다음 아래 알고리즘은 A의 대략적인 카디널리티를 결정한다.

절차 FM-스케치: 0 ~ L - 1 do BITMAP[i] :=0 do x do BITMAP[index] = 0이면 색인 : ρ(hash(x)], B : 대부분의 0 bit map[return] b ^ 왼쪽 0 bit의 위치

데이터 스트림에 N개의 고유 요소가 있는 경우null

• $i{\displaystyle }$ ${\displaystyle \gg }$ ${\displaystyle \log (}$ ( N${\displaystyle }$)$${\$displaystyle$ i$\gg \log(N)}$의 경우 BITMAP[i]는 확실히 0이다.
• $i{\displaystyle }$ ${\displaystyle \ll }$ ${\displaystyle \log }$ ${\displaystyle }$( N${\displaystyle }$) ${\displaystyle i\ll \log(N)}$의 경우 BITMAP[i]는 확실히 1이다.
• $i{\displaystyle }$ ${\displaystyle \approx }$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle \log }$(N )${\displaystyle i\$ 약 $\log(N)}$의 경우 BITMAP[i]는 0과 1의 프링이다.

K 최소값 알고리즘

이전의 알고리즘은 Flajolet과 Martin에 의한 데이터 스트림에서 F의₀ 근사치를 위한 첫 번째 시도를 설명한다.그들의 알고리즘은 해시공간에 해시값을 균일하게 분포시킨다고 가정하는 임의 해시함수를 선택한다.null

Bar-Yossef 등에서는 데이터 스트림의 고유 요소 수를 결정하기 위한 k-최소값 알고리즘을 도입했다.그들은 $h{\displaystyle }$ :${\displaystyle }$[${\displaystyle 0}$,${\displaystyle 1}$]로 정규화할 수 있는 유사한 해시함수 h를 h${\displaystyle }$: [ m ${\displaystyle ]}$→${\displaystyle }$[ ${\displaystyle 0}$], 1 ${\displaystyle ]}$ ${\디스플레이스타일$h:[m$]\오른쪽 화살표 [0,$1]과 같이 사용하였으나, 해시공간의 값 수에 제한 t를 고정하였다$.$t 값은 $O{\displaystyle }$(1${\displaystyle {\displaystyle \frac{{\epsilon \mathrm{}}_{}}{}}}$ 2 )${\$ O$\left({\dfrac$ {1$}{\$dfrac {$1}{\varepsilon _{2}}}\right)}($즉, 더 적은 근사값 value에는 더 많은 t가 필요하다고 가정한다.KMV 알고리즘은 해시 공간에 가장 작은 해시 값만 유지한다.After all the m values of stream have arrived, ${\displaystyle \upsilon =\mathrm {Max} (h(a_{i}))}$ is used to calculate${\displaystyle F'_{0}={\dfrac {t}{\upsilon }}}$. That is, in a close-to uniform hash space, they expect at-least t elements to be less than ${\displaystyle O({\displaystyle \frac{t}{F_0}}}$${\$$F_{0}}\오른쪽$ .

는 a1에 대한 할 절차 한국의 2K-Minimum 값 초기화 1t값 만약 h(를)<>Max(한국) 다음 한국에서 Max(한국)을 제거하십시오 한국 영상 끝에 복귀 t(한국) 끝나면에 삽입 h(를)을 세웠다.

KMV의 복잡성 분석

한국 알고리즘은 O형에((1ε 2)⋅ 로그⁡(m)){\displaystyle O\left(\left({\dfrac{1}{\varepsilon_{2}}}\right)\cdot \log(m)\right)}메모리 비트 공간 구현할 수 있다.각각의 해시 값 위해 O(로그 ⁡(m)){\displaystyle O(\log(m))}기억 조각들의 공간을 필요로 한다.에는 O{O\left({\dfrac{1}{\varepsilon_{2}}}\right)\displaystyle}(1ε 2)명령의 해시 값이.만약 우리가 2진 트리에서는 t해시 값을 저장한 접근 시간 줄일 수 있다.그러므로 시간 복잡도 O에⋅ 로그⁡(m)){\displaystyle O\left(\log \left({\dfrac{1}{\varepsilon}}\right)\cdot \log(m)\right)}(로그 ⁡(1ε) 줄어들 것이다.

F_k 계산 중

Alon 등은 주어진 공간과 시간 내에서 계산될 수 있는 랜덤 변수를 정의하여 F를_k 추정한다.^[3]랜덤 변수의 기대값은 F의_k 대략적인 값을 제공한다.

sequence m의 길이를 미리 알고 있다.그런 다음 랜덤 변수 X를 다음과 같이 생성하십시오.

• $p$에 인덱스가 있는 시퀀스 A의 임의 멤버를 선택하십시오_p. ${\displaystyle p_{}}$= ${\displaystyle l}$ ${\displaystyle \in }$ (${\displaystyle 1,}$ ${\displaystyle 2}$,${\displaystyle 3}$, …${\displaystyle }$,${\displaystyle }$n${\displaystyle }$) ${\displaystyle a_{p}=l\in ($1,2$,3,\ldots ,n)}$
• Let $r{\displaystyle }$=${\displaystyle }${ ${\displaystyle q}$: ${\displaystyle q}$ ${\displaystyle q}$≥ p${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle q_{}}$= ${\displaystyle l}$} $displaystyle$r$= \{q:q\geq p,a_{q}=l$는 다음 순서 A의_p 멤버 내에서 l의 발생 횟수를 나타낸다.
• 랜덤 변수 $X{\displaystyle }$= ${\displaystyle m(}$ ${\displaystyle {}^{}}$ ${\displaystyle k{}^{}}$-${\displaystyle }$( r${\displaystyle }$- ${\displaystyle 1^{}}$) k${\displaystyle {}^{}}$) ${\displaystyle X=m(r^{k}-(r-1)^{k$

Assume S₁ be of the order ${\displaystyle O(n^{1-1/k}/\lambda ^{2})}$ and S₂ be of the order ${\displaystyle O(\log(1/\varepsilon ))}$. Algorithm takes S₂ random variable ${\displaystyle Y_{1},Y_{2},...,$$Y_{S2}}:$ $중위수$ Y ${\displaystyle Y}$를 출력한다_i.$$ 여기서_ij Y는 X의 평균이며 여기서 1 j j s₁ S이다.

이제 랜덤 변수 E(X)에 대한 기대치를 계산하십시오.null

${\displaystyle {\begin{array}{lll}E(X)&=&\sum _{i=1}^{n}\sum _{i=1}^{m_{i}}(j^{k}-(j-1)^{k})\\&=&{\frac {m}{m}}[(1^{k}+(2^{k}-1^{k})+\ldots +(m_{1}^{k}-(m_{1}-1)^{k}))\\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{2}^{k}-(m_{2}-1)^{k}))+\ldots \\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{n}^{k}-(m_{n}-1)^{k}))]\\&=&\sum _{i=1}^{n}m_{i}^{k}=F_{k}\end{array}}}$

F의_k 복잡성

위에서 논의한 F를_k 계산하는 알고리즘에서 우리는 각 랜덤 변수 X가 a와_p r의 값을 저장한다는 것을 알 수 있다.따라서 X를 계산하려면 a를 저장하는_p 로그(n) 비트만 유지하고 r을 저장하는 로그(n) 비트만 유지하면 된다.랜덤 변수 X의 총 $개수$는 ${\displaystyle {S\mathrm{}}_{}}$ 1${\displaystyle {}_{}{}_{}}$ S ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}개 입니다$.$

Hence the total space complexity the algorithm takes is of the order of ${\displaystyle O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)}$

F를₂ 계산하는 더 간단한 접근 방식

이전 알고리즘은 $O{\displaystyle (n\sqrt{}}$ (${\displaystyle \log }$ ${\displaystyle m}$+ ${\displaystyle \log }$ ${\displaystyle n}$)${\displaystyle O({\sqrt{n}}(\log$ m$+\log n)})$의 순서대로$$$$ ${\displaystyle {F\mathrm{}}_{}}$ 2 ${\$}}을 계산한다.값이 {${\displaystyle }$- ${\displaystyle 1}$, ${\displaystyle 1\}}$ ${\displaystyle$\{-$1,1\}$에 매핑된 4-wise 독립 랜덤 변수를 사용하여 이 알고리즘을 단순화했다$.$

This further reduces the complexity to calculate ${\displaystyle F_{2}}$ to ${\displaystyle O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)}$

빈번한 요소

데이터 스트림 모델에서 빈번한 요소 문제는 스트림의 일부 고정된 부분 이상을 구성하는 요소 세트를 출력하는 것이다.특례는 대다수의 문제인데, 이것은 어떤 가치도 그 흐름의 과반수를 구성하는지 아닌지를 결정하는 것이다.null

좀 더 공식적으로, 긍정적인 상수를 고치십시오.c> 1, 개울의 길이를 그대로 두어라.m, 그리고 letf_i 가치의 빈도를 나타내다.i개울에빈번한 요소 문제는 { 세트를 출력하는 것이다.i f_i > m/c }.^[13]

주목할 만한 알고리즘은 다음과 같다.

• 보이어-무어 다수결 알고리즘
• 카운트-최소 스케치
• 로시 카운트
• 다단계 블룸 필터
• Misra-Gries 요약

이벤트 탐지

데이터 스트림에서 이벤트를 감지하는 것은 흔히 위에 열거한 바와 같이 중타자 알고리즘을 사용하여 이루어진다. 가장 빈번한 항목과 빈도는 이러한 알고리즘 중 하나를 사용하여 결정된다. 그러면 이전 시점보다 가장 큰 증가가 추세로 보고된다.이 접근방식은 정규화를 위해 기하급수적으로 가중된 이동 평균과 분산을 사용하여 개선할 수 있다.^[14]null

고유 요소 계산

하천에서₀ 구별되는 원소의 수(F 순간이라고도 함)를 세는 것도 잘 연구된 문제다.그것에 대한 첫 번째 알고리즘은 Flajolet과 Martin에 의해 제안되었다.2010년, 다니엘 케인, 젤라니 넬슨, 데이비드 우드러프는 이 문제에 대해 점증적으로 최적의 알고리즘을 발견했다.^[15]O(수신² + 로그 d) 공간을 사용하며, O(1) 최악의 경우 업데이트 및 보고 시간은 물론 r = Ω(log(1/message)/log(1/message)인 r-wise 독립 해시 패밀리도 사용한다.null

엔트로피

The (empirical) entropy of a set of frequencies ${\displaystyle \mathbf {a} }$ is defined as ${\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}}$, where ${\displaystyle m=\sum _{i=1}^{n}a_{i}$$}$.

온라인 학습

교육 세트를 통해 단일 패스로 모델(예: 분류자)을 학습하십시오.null

• 피쳐 해싱
• 확률적 경사 강하강

하한

하한은 연구된 많은 데이터 스트리밍 문제에 대해 계산되었다.지금까지, 이러한 하한을 계산하는 가장 일반적인 기술은 의사소통의 복잡성을 이용하는 것이었다.^{[citation needed]}null

참고 항목

• 데이터 스트림 마이닝
• 데이터 스트림 클러스터링
• 온라인 알고리즘
• 스트림 처리
• 순차 알고리즘

메모들

참조

• Alon, Noga, Matias, Yossi;Szegedy, 마리오(1999년),"주파수 순간으로 그 공간 복잡도"면 필기장 컴퓨터 및 시스템 과학, 58(1):137–147, doi:10.1006/jcss.1997.1545, ISSN 0022-0000.첫째 Alon, Noga, Matias, Yossi;Szegedy, 마리오(1996년),"주파수 순간으로 그 공간 복잡도"28ACM심포지움 이론 컴퓨팅(STOC 1996년)에 회보를 대신하여 서명함. 20–29, CiteSeerX 10.1.1.131.4984, doi:10.1145/237814.237823, 아이 에스비엔 978-0-89791-785-8, S2CID 1627911된다.
• Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002), "Models and issues in data stream systems", Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) (PDF), pp. 1–16, CiteSeerX 10.1.1.138.190, doi:10.1145/543613.543615, ISBN 978-1581135077, S2CID 2071130.
• Gilbert, A. C.; Kotidis, Y.; Muthukrishnan, S.; Strauss, M. J. (2001), "Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries" (PDF), Proceedings of the International Conference on Very Large Data Bases: 79–88.
• 케인, 다니엘 M., 넬슨, Jelani,'우드러프', 데이비드 P.(2010년)."그 고유 요소를 problem을 위한 최적의 알고리즘".데이터베이스 시스템의 원리에twenty-ninth ACMSIGMOD-SIGACT-SIGART 심포지엄의 논문집.PODS '10.뉴욕 뉴욕 USA:ACM.를 대신하여 서명함. 41–52.CiteSeerX 10.1.1.164.142. doi:10.1145/1807085.1807094.아이 에스비엔 978-1-4503-0033-9.S2CID 10006932..
• Karp, R. M.; Papadimitriou, C. H.; Shenker, S. (2003), "A simple algorithm for finding frequent elements in streams and bags", ACM Transactions on Database Systems, 28 (1): 51–55, CiteSeerX 10.1.1.116.8530, doi:10.1145/762471.762473, S2CID 952840.
• Lall, Ashwin, Sekar, Vyas, Ogihara, Mitsunori, 수, 준;장, 후이(2006년),"네트워크 트래픽의 엔트로피의 추정을 위한 데이터 알고리즘 스트리밍", 합동 국제 회의의 컴퓨터 시스템(ACMSIGMETRICS 2006년)(PDF)페이지의 주 145, doi:10.1145/1140277.1140295, hdl:1802/2537, 아이 에스비엔 978-1595933195, S2CI의 측정 및 모델링에 논문집.D 240982[영구적인 죽은 링크].
• Xu, Jun (Jim) (2007), A Tutorial on Network Data Streaming (PDF).
• Heath, D, Kasif, S, Kosaraju, R, Salzberg, S, S, Sullivan, G, "Learning Named Concepts With Limited Storage", IJCAI'91 Procedures 진행 - 제2권 777-782쪽, Morgan Kaufmann Pubers Inc.샌프란시스코, CA, 미국 ©1991
• Morris, Robert (1978), "Counting large numbers of events in small registers", Communications of the ACM, 21 (10): 840–842, doi:10.1145/359619.359627, S2CID 36226357.