비디오: Streaming Algorithms (Jessica Su) 2025
많은 스트리밍 알고리즘의 중심에는 블룸 필터가 있습니다. Burton H. Bloom이 거의 50 년 전에 컴퓨터 과학이 여전히 어려웠던시기에이 알고리즘을 만든 사람의 원래 의도는 공간 (메모리) 및 / 또는 시간 (복잡성)을 허용 가능한 오류. 그의 원래 논문의 제목은 허용 가능한 오류가있는 해시 코딩의 공간 / 시간 트레이드 오프 입니다.
블룸 (Bloom)이 자신의 알고리즘에 동기를 부여한 공간과 시간에 대해 궁금해 할 수 있습니다. 이전에 논의 된 일부 데이터 구조를 사용하여 요소가 이미 스트림에 표시되었는지 여부를 결정해야한다고 가정 해보십시오. 스트림에서 무언가를 찾는 것은 녹음 및 검색이 빠르기 때문에 해시 테이블이 이상적인 선택 인 것으로 나타납니다. 해시 테이블 에는 단순히 레코드하고 저장하려는 요소를 추가해야합니다. 해시 테이블에서 요소를 쉽게 조작하는 값을 사용하기 때문에 요소 자체가 아닌 요소를 나타내는 데 사용되므로 해시 테이블에서 요소를 복구하는 속도가 빠릅니다. 그러나 두 요소와 그 요소에 대한 색인을 저장하는 데는 한계가 있습니다. 해시 테이블이 처리 할 수있는 것보다 더 많은 요소 (예: 연속적이고 잠재적으로 무한 스트림의 요소)를 처리하면 결국 어느 시점에서 메모리 문제가 발생하게됩니다.
비트 벡터:요소의 각 비트가 0 또는 1 일 수있는 비트 요소 목록입니다. 목록은 long m이라고 불리는 비트의 수. m이 클수록 크기가 최적으로 정의되는 방법이 있지만 더 좋습니다.
- 일련의 해시 함수: 각 해시 함수는 다른 값을 나타냅니다. 해시 함수는 데이터를 신속하게 처리하고 해시의 최소 출력 값에서 최대 출력 값에 이르는 균일하게 분포 된 결과를 생성 할 수 있습니다.
