데이터 스트림의 임의의 하위 집합을 유지하는 방법은 무엇입니까?

Question

내 서버를 통과하는 이벤트 스트림이 있습니다. 모든 것을 저장할 수는 없지만 일부를 정기적으로 처리 할 수 ​​있기를 원합니다. 그래서, 내가 본 모든 것을 무작위로 샘플링하는 스트림의 하위 집합을 유지하려고하지만 최대 크기로 제한됩니다.

따라서 새 항목마다 저장 된 집합에 추가할지 또는 삭제해야하는지 결정하는 알고리즘이 필요합니다. 추가하고 이미 한계에 도달했다면 이전 항목 중 하나를 제거하는 알고리즘이 필요합니다.

분명히 내가 제한 한도에 도달하면 (모든 것을 저장하면) 이것은 쉽습니다. 그러나 한도를 초과하면 오래된 아이템이나 새로운 아이템에 편향되지 않고 어떻게 무작위로 좋은 샘플링을 유지할 수 있습니까? 당신이 찾고있는 무엇을 정확하게하지

Answer 1

this paper 동안

덕분에, 그것은 검색에 좋은 출발점이 될 수있다.

Answer 2

은 선입 선출 (FIFO) 대기열에 샘플을 저장합니다.

샘플 사이에 너무 많은 이벤트의 샘플링 속도를 설정하거나 이벤트 패턴에 따라 비트를 임의로 설정하십시오.

마다 n 번째 이벤트를 저장하거나 요금이 알려줄 때마다 대기열의 끝까지 붙여 넣습니다.

크기가 너무 큰 경우 상단에서 튀어 나오십시오.

Answer 3

각 이벤트를 기록 할 확률을 지정하고 이벤트를 인덱싱 가능한 데이터 구조에 저장하십시오. 구조체의 크기가 임계 값에 도달하면 임의의 요소를 제거하고 새 요소를 추가합니다. 루비에, 당신이 할 수 있습니다 : 이것은 당신의 최대 크기 및 이벤트가 발생했을 때 향해 비 바이어스를 해결

@storage = [] 
prob = 0.002 

while (message = getnextMessage) do 
    @storage.delete((rand() * @storage.length).floor) if @storage.length > MAX_LEN 
    @storage << message if (rand() < prob) 
end 

. 저장된 요소를 버킷으로 분할 한 다음 하나 이상의 요소가있는 버킷에서 요소를 제거하여 삭제할 요소를 선택할 수도 있습니다. 양동이 방법을 사용하면 예를 들어 한 시간마다 하나씩 유지할 수 있습니다.

샘플링 이론은 Big Math입니다. 이것에 대한 평신도의 생각 이상을 필요로한다면 해당 지역의 자격을 갖춘 수학자와 상담해야합니다.

Answer 4

이것은 수신 할 총 이벤트 수를 알지 못하며 서브 세트에서 최소 요소 수는 필요 없다고 가정합니다.

arr = arr[MAX_SIZE] //Create a new array that will store the events. Assuming first index 1. 
counter = 1 //Initialize a counter. 

while(receiving event){ 
    random = //Generate a random number between 1 and counter 
    if(counter == random){ 
    if(counter <= MAX_SIZE){ 
     arr[counter] = event 
    } 
    else{ 
     tmpRandom = //Generate a random number between 1 and MAX_SIZE 
     arr[tmpRandom] = event 
    } 
    } 
    counter =+ 1 

} 

Answer 5

이것은 일반적인 인터뷰 질문입니다.

쉽게 할 수있는 한 가지 방법은 n 번째 요소를 확률 k/n (또는 1보다 작은 값)로 저장하는 것입니다. 새 샘플을 저장하기 위해 요소를 제거해야하는 경우 임의의 요소를 제거하십시오.

이렇게하면 n 개의 요소 중 일정한 임의의 부분 집합을 얻을 수 있습니다. 당신이 n을 모른다면, 그것을 추정하고 대략 균일 한 부분 집합을 얻을 수 있습니다.

Answer 6

이것은 임의 샘플링이라고합니다.출처 : http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k]; // result 
integer i, j; 

// fill the reservoir array 
for each i in 1 to k do 
    R[i] := S[i] 
done; 

// replace elements with gradually decreasing probability 
for each i in k+1 to length(S) do 
    j := random(1, i); // important: inclusive range 
    if j <= k then 
     R[j] := S[i] 
    fi 
done 

괜찮은 설명/증명 : http://propersubset.com/2010/04/choosing-random-elements.html