나는 회원 테스트 수행을 위해 블룸 필터를 사용해 보았습니다. 저는 약 100 회의 충돌 만 허용하면서 800 억 개의 항목에 대한 멤버십 테스트를 수행하고자합니다. 즉, 100 개의 항목 만 잘못된 결과를 얻을 수 있습니다.블룸 필터의 대안
블룸 필터에 의해 달성 될 수 있지만 입력 당 필요한 비트 수와 허위 양수 율이 허용되는 해시 함수의 수를 결정하는 공식을 사용한다는 것을 알고 있습니다. 나는 270GB의 메모리와 19 개의 해쉬 함수를 사용하여 끝낼 것이라고 생각했다.
나는 또한 Cuckoo 필터를 살펴 봤지만 메모리 요구 사항이 내 요구 사항과 일치하지 않습니다. 요소
누군가 내 요구 사항을 달성하는 데 도움이 될 수있는 위에 언급 된 것 이외의 확률 론적 데이터 구조를 제안 할 수 있습니까?
해시 함수의 수와 관련된 문제는 실제로 문제가되지 않습니다. 많은 해시 출력을 가진 단일 해시 함수를 선택하고 개별 해시 함수에서 나온 것처럼 비트를 나눕니다. 여기에서 귀하가 진정으로 직면 한 문제는 저장 공간에 대한 오 탐지율의 균형입니다.
당신은가 난 단지 약 100 충돌 즉, 100 개의 항목이 주어진 거짓 긍정적 인 결과가 될 수 일어날 수와 800 억 개 항목에 회원 테스트를 수행하고자 말했다. 지도에
항목은, 정의에 의해, 거짓 긍정적이 될 수 없습니다. 그들은 사실 긍정입니다.
다음 질문은 "테스트 할 대상 항목 수 : ?"에 대한 100 개의 오탐이 있습니까? 만약 그 해답이 800 억이라는 이상한 것이라면, 당신은 2^-29보다 적은 100/80000000000 = 1/800,000,000의 오 탐지율을 요구하고 있습니다.
Bloom 필터 또는 뻐꾹 필터와 같은 대략적인 멤버십 데이터 구조의 최소 공간은 ng 1/ε 비트입니다. 여기서 n은 구조의 요소 수이고, lg는 로그 기준 2이며, ε은 false입니다 긍정적 인 비율. 즉, 80 억 회당 100과 같이 위양성 비율을 달성하려면 요소 당 29 비트 이상이 필요합니다. 요소 당 6 비트는 1.56 %의 오 탐지율을 나타냅니다. . 이는 800 억 회당 12 억 5 천만 개, 즉 6400 개당 100 개입니다.
알고있는 한 실제적인 데이터 구조는 거의 실현되지 않았습니다. 블룸 필터는 항목 당 1/ε 비트 이상을 사용하기 때문에 예를 들어 사용되지 않습니다. 뻐꾸기 필터는 항목 당 적어도 두 개의 추가 메타 데이터 비트를 사용하고 lg n으로 비례하는 비트 당 항목 비율을 가지기 때문에 뻐꾹 필터는 사용할 수 없습니다.
필자는 메모리 요구 사항이 더 많은 경우가 될 것임을 알고 있습니다. 그러나 단일 해시 함수를 사용하고 비트를 나누는 제안은 흥미 롭습니다. 이것을 구현해 본 결과와 별도의 해시 함수를 사용하여 얻을 수있는 결과와 비슷한 것을 발견 했습니까? –
예, 구현했으며 괜찮 았습니다. 그러나 품질이 낮은 해시 패밀리에서는 작동하지 않습니다. 이 마진은 너무 작아서 더 완전한 답을 포함 할 수 없지만 vhash, 보편적 해싱, SipHash 및 이와 유사한 것들을 읽습니다. – jbapple
거짓 데이터 양수가 .00000000125이고 항목 수가 제한되지 않았더라도 60GB 만 사용하면 80 억 항목을 구분할 수있는 데이터 구조를 찾지 못할 것 같습니다. 해시 함수 증명할 수학은 없지만 이론적으로 가능한 범위를 넓히는 것처럼 보입니다. –
좋아요. 내 기억이 늘어나거나 거짓 긍정적 인 비율이 항목의 1 %까지 올라간다면, 블룸 필터를 사용 사례로 사용하거나 다른 선택적인 데이터 구조가 있습니까? –