저수지 시료 채취

저장장치 샘플링은 한 번의 통과로 알 수 없는 크기 $n$ 의 모집단에서 $k개$ 항목의 단순한 무작위 샘플을 대체하지 않고 선택하기 위한 무작위화된 알고리즘의 제품군이다.모집단 $n$ 의 크기는 알고리즘에 알려져 있지 않으며 일반적으로 모든 $n개$ 의 항목이 메인 메모리에 맞기에는 너무 크다.모집단은 시간이 지남에 따라 알고리즘에 공개되며, 알고리즘은 이전 항목을 돌아볼 수 없다.어느 지점에서든 알고리즘의 현재 상태는 지금까지 본 모집단의 일부에 걸쳐 크기 $k$ 를 대체하지 않고 단순한 무작위 표본을 추출할 수 있어야 한다.

동기

우리가 한 번에 하나씩 일련의 항목들을 본다고 가정합시다.우리는 10개의 아이템을 기억 속에 간직하고 싶고, 순서에서 무작위로 선정되기를 원한다.항목 $n개$ 의 총 개수를 알고 임의로 항목에 접근할 수 있다면 해결책은 쉽다: 동일한 확률로 1과 $n$ 사이의 10개의 구별되는 지수 $i$ 를 선택하고 i번째 요소를 유지한다.문제는 우리가 항상 정확한 $n$ 을 미리 알고 있는 것은 아니라는 것이다.

단순 알고리즘

흔히 알고리즘 R으로 알려진 단순하고 인기 있지만 느린 알고리즘은 앨런 워터맨 때문이다.^[1]

알고리즘은 입력의 첫 $번째$ k 항목을 포함하는 k $크기$ 의 저장소를 유지함으로써 작동한다.그 후 입력이 소진될 때까지 나머지 항목에 대해 반복한다.단일 기반 어레이 인덱싱을 사용하여 $i>k$ > $i>k$ $i>k$ 을(를) 현재 고려 중인 항목의 인덱스가 되도록 $i>k$ 한다.그런 다음 알고리즘은 1과 $i$ 사이에 임의의 $숫자$ j를 생성한다. $j$ 가 최대 $k$ 인 경우 $i$ ^th 항목이 선택되고 현재 저장소의 j-th 위치를 차지하고 있는 항목 중 하나를 대체한다.그렇지 않으면 해당 품목이 폐기된다.사실상, 모두를 위해 나는, 입력의ith 요소 가능성을 가지고 저장고에 포함될 k/. 마찬가지로, 각 반복 주기에서 저장고 배열의jth 현재 요소 새로운ith 요소로 확률 1/k×로 대체되 k/나는 1/나는{\displaystyle 1/k\times k/i원 선택된다{\displaystyle k/i}선택된다.=1/i} $1/k\times k/i=1/i$ 알고리즘 실행이 완료되면 입력 모집단의 각 항목은 저장소에 대해 선택될 확률( $k/n$ : k $k/n$ ${\displaystyle k/n$ 이 동일하다.

{\frac {k}{j}}\time {\Bigl (}1-{\frac {1}{j+1}}{\\)Bigr )}\time {\Bigl (}1-{\frac {1}{j+2}}:{\\)Bigr )}\time {\Bigl (}1-{\frac {1}{j+3}}{\\\Bigr )}\times \cdots \times {\Bigl (}1-{\frac {1}{n}}{\Bigr )}={\frac {k}{j}}\prod _{i=j+1}^{n}{\Bigl (}1-{\frac {1}{i}}{\Bigr )}={\frac {k}{n}}.

여기, kj{\displaystyle{\frac{k}{j}}}은jth 요소를 물색한 확률,는 동안 나는 × 1− k1k=1− 1나는{\displaystyle 1-{\frac{k}{나는}}\times{\frac{1}{k}}=1-{\frac{1}{나는}}}은 선택의 상호 보완적인 발생 확률은ith 요소 그 후에(확률 k나는{\displaystyle{\frac. {k}{ $i$ 을(를) 선택하고 이전에 선택한 $j$ ^th 요소를 그 요소로 교체(후기 ${\frac {1}{k}}$ $i>j$ > $i>j$ > ${\$ $displaystyle {\$ $frac$ ${$ 1 $displaystyle i}.$

(* S는 샘플링할 품목이 있고, R은 결과를 포함할 것이다 *) 저장기표본(S[1..n], R[1..k])   // 탱크 어레이를 채우십시오.   을 위해 i := 1 로 k       R[i] := S[i]    // 원소를 점차 감소하는 확률로 대체   을 위해 i := k+1 로 n     (* 랜덤정수(a, b)가 포함 범위 {a, ..., b} *에서 균일한 정수를 생성함     j := 랜덤인테거(1, i)     만일 j <= k         R[j] := S[i]

개념적으로 간단하고 이해하기 쉽지만, 이 알고리즘은 폐기되는 항목을 포함하여 입력의 각 항목에 대해 무작위 번호를 생성해야 한다.따라서 점증적 작동 시간은 $O(n)$ ( n $O(n)$ ) $O(n)$ 입니다 $O(n)$ 이는 입력 모집단이 클 경우 알고리즘이 불필요하게 느려지게 한다.

최적 알고리즘

알고리즘 L은^[2] 다음 항목이 저장소에 들어가기 전에 폐기되는 항목 수를 계산하여 이 알고리즘을 개선한다.중요한 관찰은 이 숫자가 기하 분포를 따르므로 일정한 시간에 계산될 수 있다는 것이다.

(* S는 샘플링할 품목이 있고, R은 결과를 포함할 것이다 *) 저장기표본(S[1..n], R[1..k])   // 탱크 어레이를 채우십시오.   을 위해 i = 1 로 k       R[i] := S[i]    (* 랜덤으로 균일(0,1) 랜덤 번호 생성 *)   W := 생략하다(통나무를 하다(무작위의())/k)    하는 동안에 i <= n       i := i + 마루를 깔다(통나무를 하다(무작위의())/통나무를 하다(1-W)) + 1       만일 i <= n           (* 저장소의 임의 항목을 항목 i *로 교체)           R[랜덤인테거(1,k)] := S[i]  // 1과 k 사이의 랜덤 지수(포함)           W := W * 생략하다(통나무를 하다(무작위의())/k)

이 알고리즘은 저장소의 일부가 되는 각 항목에 대해 3개의 무작위 번호를 계산하며, 그렇지 않은 항목에 대해서는 어떠한 시간도 소비하지 않는다.따라서 예상 실행 시간은 $O(k(1+\log(n/k)))$ ( 1 $O(k(1+\log(n/k)))$ + $O(k(1+\log(n/k)))$ log $O(k(1+\log(n/k)))$ / $O(k(1+\log(n/k)))$ ) $){\displaystyle O(k(1+\log(n$ /k $)))}$ 이며 $O(k(1+\log(n/k)))$ ^[2] 이는 최적이다.^[1]동시에 효율적으로 구현하는 것이 간단하며, 이국적이거나 계산하기 어려운 분포로부터 무작위적인 편차에 의존하지 않는다.

임의 정렬 포함

입력의 각 항목과 균일하게 생성된 무작위 숫자를 연관시키면 가장 큰(또는 동등하게, 가장 작은) 연관 값을 $가진$ k 항목이 단순 랜덤 표본을 형성한다.^[3]따라서 단순 저장장치 샘플링은 우선순위 대기열에서 현재 가장 큰 연관 값을 가진 k $항목$ 을 유지한다.

(* S는 샘플링할 아이템의 스트림이다. S.Current가 스트림에서 현재 항목을 반환함 S.다음 진전은 다음 위치로 스트림 최소 우선순위 지원: 카운트 -> 우선순위 대기열에 있는 항목 수 최소 -> 모든 항목의 최소 키 값 반환 추출-최소() -> 최소 키로 항목 제거 삽입(키, 항목) -> 지정한 키로 항목 추가 *) 저장기표본(S[1..?])   H := 새로운 분-우선순위-줄을 서다   하는 동안에 S 가지다 자료     r := 무작위의()   // 0과 1 사이의 균일하게 무작위, 배타적     만일 H.카운트 < k       H.삽입하다(r, S.현재)     다른       // 관련 키가 가장 큰 k 항목 유지       만일 r > H.최소         H.추출하다-분()         H.삽입하다(r, S.현재)     S.다음   돌아오다 항목들 에 H

이 알고리즘의 예상 실행 시간은 $O(n+k\log k\log(n/k))$ + k $O(n+k\log k\log(n/k))$ $O(n+k\log k\log(n/k))$ k $O(n+k\log k\log(n/k))$ $O(n+k\log k\log(n/k))$ ( $O(n+k\log k\log(n/k))$ / $O(n+k\log k\log(n/k))$ ) ${\displaystyle$ O $(n+k\log k\log(n/k))}$ 이며 $O(n+k\log k\log(n/k))$ , 주로 가중치가 있는 항목까지 쉽게 확장될 수 있기 때문에 관련이 있다.

가중 랜덤 표본 추출

일부 적용에서는 각 항목과 관련된 가중치에 따라 항목의 표본 추출 확률을 요구한다.예를 들어, 사용자 경험에 대한 전반적인 영향을 분석하기 위해 샘플이 수행된 횟수만큼 가중치가 있는 검색 엔진에서 쿼리를 샘플링해야 할 수 있다. $아이템$ 의 무게는 $w_{i}$ ${\$ 가 $w_{i}$ 하고, 모든 무게의 합은 $w$ 가 되도록 한다.세트의 각 항목에 할당된 가중치를 해석하는 두 가지 방법이 있다.^[4]

각 라운드에서 선택되지 않은 모든 항목이 해당 라운드에서 선택될 확률은 선택되지 않은 모든 항목의 가중치에 비례한다. $X$ 가 현재 샘플인 경우, 현재 라운드에서 $i\notin X$ i $i\notin X$ X ${\displaystyle i\notin X$ $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ 을 $i\notin X$ (를) 선택할 $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ 은 w $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ / $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ ( $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ - $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ j $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ ∈ X $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ ) $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ {\ $displaystyle \text w_{i}/(W-\sum$ _{ $j_{w_{j}}}})$ 입니다 $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$
랜덤 표본에 포함되는 각 항목의 확률은 상대 가중치( $w_{i}/W$ i $w_{i}/W$ ${\displaystyle w_{i}/W})$ 에 비례한다 $w_{i}/W$ k $k=n$ = n $k=n$ 과 같은 $k=n$ 에는 이 $k=n$ 을 달성할 수 없을 수 있다 $k=n$

알고리즘 A-Res

해석 1을 사용하는 Efraimidis와 Spirakis에 의해 다음과 같은 알고리즘이 주어졌다.^[5]

(* S는 샘플링할 아이템의 스트림이다. S.Current가 스트림에서 현재 항목을 반환함 S.Weight는 스트림에서 현재 항목의 가중치를 반환함 S.다음 진전은 다음 위치로 스트림 전원 연산자는 ^로 표시된다. 최소 우선순위 지원: 카운트 -> 우선순위 대기열에 있는 항목 수 최소 () -> 모든 항목의 최소 키 값 반환 추출-최소() -> 최소 키로 항목 제거 삽입(키, 항목) -> 지정한 키로 항목 추가 *) 저장기표본(S[1..?])   H := 새로운 분-우선순위-줄을 서다   하는 동안에 S 가지다 자료     r := 무작위의() ^ (1/S.무게)   // 무작위 추출은 (0,1)에서 균일하게 무작위 숫자를 생성한다.     만일 H.카운트 < k       H.삽입하다(r, S.현재)     다른       // 관련 키가 가장 큰 k 항목 유지       만일 r > H.최소         H.추출하다-분()         H.삽입하다(r, S.현재)     S.다음   돌아오다 항목들 에 H

이 알고리즘은 항목의 키 생성을 제외하고 랜덤 정렬을 사용한 저장장치 샘플링에 주어진 알고리즘과 동일하다.알고리즘은 각 항목에 키 $r^{1/w_{i}}$ $r^{1/w_{i}}$ / $r^{1/w_{i}}$ i ${\$ r $^{1/w_{i}}$ 을 할당하고 여기서 $r^{1/w_{i}}$ $r$ 은 임의의 숫자인 다음 가장 큰 키를 가진 k $항목$ 을 선택하는 것과 같다.동등하게, 이 알고리즘의 보다 수치적으로 안정된 제형은 키를 $-\ln(r)/w_{i}$ - $-\ln(r)/w_{i}$ $-\ln(r)/w_{i}$ ( $-\ln(r)/w_{i}$ ) $-\ln(r)/w_{i}$ / w $-\ln(r)/w_{i}$ ${\$ -\ $ln(r)/w_{i}}$ 로 계산하고 $-\ln(r)/w_{i}$ 가장 작은 $키$ 로 k 항목을 선택한다.^[6]^{[failed verification]}

알고리즘 A-ExpJ

다음 알고리즘은 에프레미디스(Efraimidis)와 스피라키스(Spirakis)가 제공하는 A-Res(A-Res)의 보다 효율적인 버전이다.^[5]

(* S는 샘플링할 아이템의 스트림이다. S.Current가 스트림에서 현재 항목을 반환함 S.Weight는 스트림에서 현재 항목의 가중치를 반환함 S.다음 진전은 다음 위치로 스트림 전원 연산자는 ^로 표시된다. 최소 우선순위 지원: 카운트 -> 우선순위 대기열의 항목 수 우선 순위 대기열에 있는 모든 항목의 최소 -> 최소 키 추출-최소() -> 최소 키로 항목 제거 삽입(키, 항목) -> 지정한 키로 항목 추가 *) 저장기샘플위드점프(S[1..?])   H := 새로운 분-우선순위-줄을 서다   하는 동안에 S 가지다 자료 그리고 H.카운트 < k     r := 무작위의() ^ (1/S.무게)   // 무작위 추출은 (0,1)에서 균일하게 무작위 숫자를 생성한다.     H.삽입하다(r, S.현재)     S.다음   X := 통나무를 하다(무작위의()) / 통나무를 하다(H.최소) // 이것은 뛰어넘어야 할 무게의 양이다.   하는 동안에 S 가지다 자료     X := X - S.무게     만일 X <= 0       t := H.최소 ^ S.무게       r := 무작위의(t, 1) ^ (1/S.무게) // 랜덤(x, y)은 (x, y)에서 균일하게 랜덤 숫자를 생성함            H.추출하다-분()       H.삽입하다(r, S.현재)        X := 통나무를 하다(무작위의()) / 통나무를 하다(H.최소)     S.다음   돌아오다 항목들 에 H

이 알고리즘은 A-Res에서 사용되는 것과 동일한 수학적 특성을 따르지만, 각 항목에 대한 키를 계산하고 그 항목의 삽입 여부를 확인하는 대신, 삽입될 다음 항목으로 지수 점프를 계산한다.이렇게 하면 각 품목에 대해 무작위 변동을 생성하지 않아도 되는데, 이것은 비용이 많이 들 수 있다.필요한 무작위 변수의 수는 $O(n)$ 대로 $O(k\log(n/k))$ O $O(n)$ ( $O(n)$ ) $O(n)$ 에서 $O(k\log(n/k))$ ( $O(k\log(n/k))$ log $O(k\log(n/k))$ ( $O(k\log(n/k))$ $O(k\log(n/k))$ $O(k\log(n/k))$ ) $O(k\log(n/k))$ {\ $displaystyle O(k\log(n/k)})$ 로 $O(n)$ 감소하며, $n$ 서 $k$ ${\displaysty k}$ 은 $k$ 저장소의 크기, n ${\displaystysty n}$ 은 $n$ 스트림의 항목 수입니다.^[5]

알고리즘 A-차오

M. T. Chao는 해석 2를 사용하여 다음과 같은 알고리즘을 제공했다.^[7]

(* S는 샘플링할 품목이 있고, R은 결과를 포함할 것이다. 무게는 각 품목에 대한 무게를 포함한다. *) 웨이트레저부아르 주-차오(S[1..n], R[1..k])   WSum := 0   // 탱크 어레이를 채우십시오.   을 위해 i := 1 로 k       R[i] := S[i]       WSum := WSum + S[i].무게   을 위해 i := k+1 로 n     WSum := WSum + S[i].무게     p := S[i].무게 / WSum // 이 항목의 확률     j := 무작위의();          // 0과 1 사이의 균일하게 무작위     만일 j <= p               // 확률에 따라 항목 선택         R[랜덤인테거(1,k)] := S[i]  //교체를 위해 저장소에서 선택 항목 변경

각 품목에 대해 상대 중량을 계산하여 저장소에 추가할지 여부를 랜덤하게 결정하는 데 사용한다.항목을 선택한 경우, 저장소의 기존 항목 중 하나를 균일하게 선택하고 새 항목으로 교체한다.여기서의 요령은 저수지에 있는 모든 항목의 확률이 이미 무게에 비례하는 경우, 균일하게 어떤 품목을 교체할 것인지를 선택함으로써 모든 품목의 확률은 교체 후에도 무게에 비례하는 상태를 유지한다는 것이다.

알고리즘 A-차오(점프 포함)

다른 알고리즘과 마찬가지로 무작위 가중치를 계산할 수 있다.j항목의 확률 질량 값을 빼는 동안 건너뛰고j > 0, 생성해야 하는 무작위 번호 수 감소.^[4]

(* S는 샘플링할 품목이 있고, R은 결과를 포함할 것이다. 무게는 각 품목에 대한 무게를 포함한다. *) 웨이트레저부아르 주-차오(S[1..n], R[1..k])   WSum := 0   // 탱크 어레이를 채우십시오.   을 위해 i := 1 로 k       R[i] := S[i]       WSum := WSum + S[i].무게   j := 무작위의() // 0과 1 사이의 균일하게 무작위   p노네 := 1 // 지금까지 선택된 항목이 없을 확률(이 점프에서)   을 위해 i := k+1 로 n     WSum := WSum + S[i].무게     p := S[i].무게 / WSum // 이 항목의 확률     j -= p * p노네     p노네 := p노네 * (1 - p)     만일 j <= 0         R[랜덤인테거(1,k)] := S[i]  //교체를 위해 저장소에서 선택 항목 변경         j = 무작위의()         p노네 := 1

피셔-예이츠 셔플과의 관계

한 사람이 카드 한 벌에서 $무작위$ 카드를 뽑고 싶다고 가정해보자.자연스럽게 접근하는 것이 갑판을 섞은 다음 상위 k $카드$ 를 가져가는 것이다.일반적인 경우, 덱에 있는 카드 수를 미리 알 수 없는 경우에도 셔플이 작동해야 하며, 피셔-예이츠 셔플의 내부 버전에서 만족하는 조건은 다음과 같다.[8]

(* S에 입력, R에 출력 순열 * 포함) 셔플(S[1..n], R[1..n])   R[1] := S[1]   을 위해 i 로부터 2 로 n 하다       j := 랜덤인테거(1, i)  // 포함 범위       R[i] := R[j]       R[j] := S[i]

나머지 카드는 섞었지만 현재 상황에서는 첫 번째 $k$ 만 중요하다는 점에 유의하십시오.따라서 배열 $R$ 은 셔플을 수행하는 동안 첫 $번째$ k 위치에서 카드만 추적하면 돼 필요한 메모리 양이 줄어든다. $R$ 을 길이 $k$ 로 자르면 알고리즘이 그에 따라 수정된다.

(* S는 샘플링할 품목이 있고, R은 결과를 포함할 것이다 *) 저장기표본(S[1..n], R[1..k])   R[1] := S[1]   을 위해 i 로부터 2 로 k 하다       j := 랜덤인테거(1, i)  // 포함 범위       R[i] := R[j]       R[j] := S[i]   을 위해 i 로부터 k + 1 로 n 하다       j := 랜덤인테거(1, i)  // 포함 범위       만일 (j <= k)           R[j] := S[i]

첫 $번째$ k 카드의 순서는 중요하지 않기 때문에 첫 번째 루프를 제거할 수 있고 $R$ 을 초기화할 수 있어 입력의 첫 $번째$ k 항목이 될 수 있다.이것은 알고리즘 R을 산출한다.

통계적 속성

저수지 방법의 선정 확률은 차오(1982년)^[7]와 틸레(2006년)에서 논의한다.^[9]1차 선택 확률은 $k/n$ ${\displaystyle k/n}($ 또는 Chao의 절차의 경우 임의의 불평등 확률 집합에 해당)과 동일하지만, 2차 선택 확률은 원래 저장소에서 기록이 정렬되는 순서에 따라 달라진다.문제는 데빌과 틸레(2004)의 큐브 표본 추출 방식으로 극복된다.^[10]

제한 사항

저장장치 샘플링은 원하는 샘플이 주 메모리에 적합한다고 가정하며, 종종 $k$ 가 $n$ 과 일정한 독립성을 갖는다는 것을 암시한다.입력 목록의 큰 부분 집합을 선택하려는 애플리케이션(예: $k=n/3$ 번째, k $k=n/3$ = $k=n/3$ / 3 ${\displaystyle k=n/3})$ 에서는 다른 방법을 채택해야 한다. $k=n/3$ 이 문제에 대한 분산 구현이 제안되었다.^[11]

참조

^ ^a ^b Vitter, Jeffrey S. (1 March 1985). "Random sampling with a reservoir" (PDF). ACM Transactions on Mathematical Software. 11 (1): 37–57. CiteSeerX 10.1.1.138.784. doi:10.1145/3147.3165. S2CID 17881708.
^ ^a ^b Li, Kim-Hung (4 December 1994). "Reservoir-Sampling Algorithms of Time Complexity O(n(1+log(N/n)))". ACM Transactions on Mathematical Software. 20 (4): 481–493. doi:10.1145/198429.198435. S2CID 15721242.
^ Fan, C.; Muller, M.E.; Rezucha, I. (1962). "Development of sampling plans by using sequential (item by item) selection techniques and digital computers". Journal of the American Statistical Association. 57 (298): 387–402. doi:10.1080/01621459.1962.10480667. JSTOR 2281647.
^ ^a ^b Efraimidis, Pavlos S. (2015). "Weighted Random Sampling over Data Streams". Algorithms, Probability, Networks, and Games. Lecture Notes in Computer Science. 9295: 183–195. arXiv:1012.0256. doi:10.1007/978-3-319-24024-4_12. ISBN 978-3-319-24023-7. S2CID 2008731.
^ ^a ^b ^c Efraimidis, Pavlos S.; Spirakis, Paul G. (2006-03-16). "Weighted random sampling with a reservoir". Information Processing Letters. 97 (5): 181–185. doi:10.1016/j.ipl.2005.11.003.
^ Arratia, Richard (2002). Bela Bollobas (ed.). "On the amount of dependence in the prime factorization of a uniform random integer". Contemporary Combinatorics. 10: 29–91. CiteSeerX 10.1.1.745.3975. ISBN 978-3-642-07660-2.
^ ^a ^b Chao, M. T. (1982). "A general purpose unequal probability sampling plan". Biometrika. 69 (3): 653–656. doi:10.1093/biomet/69.3.653.
^ National Research Council (2013). Frontiers in Massive Data Analysis. The National Academies Press. p. 121. ISBN 978-0-309-28781-4.
^ Tillé, Yves (2006). Sampling Algorithms. Springer. ISBN 978-0-387-30814-2.
^ Deville, Jean-Claude; Tillé, Yves (2004). "Efficient balanced sampling: The cube method" (PDF). Biometrika. 91 (4): 893–912. doi:10.1093/biomet/91.4.893.
^ MapReduce의 저수지 샘플링

[vitter-1] Vitter, Jeffrey S. (1 March 1985). "Random sampling with a reservoir" (PDF). ACM Transactions on Mathematical Software. 11 (1): 37–57. CiteSeerX 10.1.1.138.784. doi:10.1145/3147.3165. S2CID 17881708.

[li-2] Li, Kim-Hung (4 December 1994). "Reservoir-Sampling Algorithms of Time Complexity O(n(1+log(N/n)))". ACM Transactions on Mathematical Software. 20 (4): 481–493. doi:10.1145/198429.198435. S2CID 15721242.

[fan-3] Fan, C.; Muller, M.E.; Rezucha, I. (1962). "Development of sampling plans by using sequential (item by item) selection techniques and digital computers". Journal of the American Statistical Association. 57 (298): 387–402. doi:10.1080/01621459.1962.10480667. JSTOR 2281647.

[efraimidis-4] Efraimidis, Pavlos S. (2015). "Weighted Random Sampling over Data Streams". Algorithms, Probability, Networks, and Games. Lecture Notes in Computer Science. 9295: 183–195. arXiv:1012.0256. doi:10.1007/978-3-319-24024-4_12. ISBN 978-3-319-24023-7. S2CID 2008731.

[EfrSpi-5] Efraimidis, Pavlos S.; Spirakis, Paul G. (2006-03-16). "Weighted random sampling with a reservoir". Information Processing Letters. 97 (5): 181–185. doi:10.1016/j.ipl.2005.11.003.

[6] Arratia, Richard (2002). Bela Bollobas (ed.). "On the amount of dependence in the prime factorization of a uniform random integer". Contemporary Combinatorics. 10: 29–91. CiteSeerX 10.1.1.745.3975. ISBN 978-3-642-07660-2.

[:1-7] Chao, M. T. (1982). "A general purpose unequal probability sampling plan". Biometrika. 69 (3): 653–656. doi:10.1093/biomet/69.3.653.

[8] National Research Council (2013). Frontiers in Massive Data Analysis. The National Academies Press. p. 121. ISBN 978-0-309-28781-4.

[9] Tillé, Yves (2006). Sampling Algorithms. Springer. ISBN 978-0-387-30814-2.

[10] Deville, Jean-Claude; Tillé, Yves (2004). "Efficient balanced sampling: The cube method" (PDF). Biometrika. 91 (4): 893–912. doi:10.1093/biomet/91.4.893.

[11] MapReduce의 저수지 샘플링

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[9]

[10]

[11]

Search