블룸 필터 또는 뻐꾸기 해싱?

Question

선호하는 대상과 그 이유는 무엇입니까?

둘 다 비슷한 작업을 수행하는 데 사용할 수 있지만 사람들이 실제 응용 프로그램에서 사용한 것과 그 이유에 대해 궁금해합니다.

Answer 1

나는 뻐꾸기 해시를 선호합니다. 더 높은 채우기 요소에서 블룸 필터와 함께 나타날 수있는 가양성에주의하십시오.
매우 큰 해시 테이블이 있고 메모리 부족 문제가있는 응용 프로그램에서 뻐꾸기 해시를 사용했습니다. 뻐꾸기 해시의 변형을 구현하려면 http://codeplex.com/ecollections에서 my eCollections 라이브러리를 참조하십시오. 내가 잘못된 반응을 견딜 수있는 공간이 중요한 경우는 적은 공간을 차지하기 때문에

종류에 관해서는,

Answer 2

, 나는 블룸 필터를 사용합니다. 그렇지 않으면 해시를 사용합니다.

Answer 3

와인이나 치즈 중 어느 것이 더 좋습니까?

꽃 필터는 높은 질의가 비용 제한된 공간, 및 대부분 부정적인 쿼리이있을 때입니다. 이 경우
키 및 4 해시 함수 당 8 비트 와 블룸 필터 당신 2.5 % 위양성율을 준다; 당신은 쿼리를 거의 번보다 빠르게 처리합니다.은 의 비용으로 1 바이트 당입니다. 이전 조건이, 말이 캐시로 해시 테이블 행동을 보유하지 않는 경우

다른 한편으로는 분명히 하나 이상의 바이트 항목 당 많이 걸릴 것이지만 -)

캐시 인 경우 뻐꾸기 해시의 하드 에지 경우를 건너 뛸 수도 있습니다. 또한 뻐꾸기 해시 테이블 (또는 선형 해시 이외의 다른 것)의 크기 증가 문제가 발생합니다.

Answer 4

뻐꾸기 필터.

"뻐꾸기 필터 : 실질적으로 꽃보다 낫다." 빈 팬, 데이빗 앤더슨, 마이클 카맨 스키, 마이클 미츤 마쳐 중 하나에서 CoNext 2014 http://dx.doi.org/10.1145/2674005.2674994

저자의 blog :

날 뻐꾸기 필터와 당신을 위해 종이에 무엇의 일부를 설명하자 . 기술적 인 논의를 피하고자한다면, 합리적으로 큰 사이즈의 세트의 경우 해당 블룸 필터와 동일한 오 탐지율, 뻐꾸기 필터가 블룸 필터보다 공간을 덜 차지하고, 조회가 빠르지 만 속도가 느립니다 삽입/생성), 놀랍게도 (Bloom 필터가 할 수없는) 키 삭제를 허용합니다. 코드를보고 싶다면 뻐꾸기 필터 코드가있는 github repository도 있습니다.

Answer 5

비슷한 상황에서는 Bloom 필터와 Cuckoo 필터가 사용되지만 차이점은 일반적으로 더 나은 선택을 결정합니다.

블룸 필터는 데이터베이스 엔진, 특히 Apache Cassandra에서 내부적으로 사용됩니다. 이유는 느린 세트 운영 비용을 줄이기 위해 다른 포스터들이 말했듯이입니다. 기본적으로, 비용이 많이 드는 작업은 "수행 할 수있는 또는 실제로 존재하지 않는"작업으로 Bloom 필터를 사용하여 수행되는 검사 수를 줄일 수 있습니다.

오늘날 SaaS 모델의 또 다른 일반적인 예는 통화 당 비용 (cost-per-call)이있는 원격 REST 서비스입니다. "이 주소가 잘못되었습니다"와 같은 이진 응답이있는 API 호출은 블룸 필터를 사용하여 중복 쿼리의 90 % 이상을 제거 할 수 있습니다! Bloom 및 Cuckoo 필터는 오탐 (false positive)이 있기 때문에 역 동작에 유용하지 않습니다. "이 주소는 유효합니까?"

Bloom 및 Cuckoo 필터에는 false negative가 없습니다. 따라서 이러한 필터는 "이것은 분명히 스팸이 아니거나 스팸 일 가능성이 있지만 사용자 권한 검사와 같은 오 탐지가 용납되지 않는 작업에는 유용하지 않습니다."와 같은 검사에 유용합니다. 이 측면에서 그들은 개념적으로 캐시의 반대로 간주 될 수 있습니다. Bloom/Cuckoo 필터와 캐시는 주로 부울 답변이있는 값 비싼 연산 비용을 줄이기 위해 사용됩니다. 단, 캐시에는 가양 성이없고 Bloom/Cuckoo에는 false negative가 없습니다. 쿠쿠 사이

주목할만한 차이점/블룸 포함

• 콤비네이션. 블룸 필터는 동일한 매개 변수로 생성되는 한 효율적으로 병합 할 수 있습니다. 빠르고 대역폭이 거의 없습니다. 그래서 대량으로 분산 된 시스템에서 빈번하게 사용되는 것을 볼 수 있으며, Bloom 필터를 교환하는 것이 빠릅니다. 뻐꾸기 필터는 쉽게 구성 할 수 없으므로 이러한 상황에서 덜 유용합니다.

• 거짓 양성율. 뻐꾸기 필터는보다 공간 효율적입니다. 두 구조의 많은 유스 케이스는 낮은 수준의 네트워킹에 초점을 맞 춥니 다. 약한 하드웨어에서 동일한 오 탐지율에 대한 Cuckoo 필터의 ~ 40 % 높은 효율성이 중요 할 수 있습니다. 참조 구현은 C++에서 각 버킷 내의 항목을 정렬하여 더 작은 지문을 저장하기 위해 버킷 내의 항목 위치를 활용하여 추가 공간을 절약합니다. 나중에 언급 할 추가 라이브러리 (내 포함)는이 작업을 수행하지 않는 것 같습니다. 누구든지 내 라이브러리를 사용한다면 추가 할 수 있습니다 :).

• 일정한 양성률. 블룸 필터는 디자인 된 크기를 초과함에 따라 점진적으로 오 탐지율을 낮 춥니 다. 영원히 물건을 계속 넣을 수는 있지만 결국 거짓 긍정적 인 비율은 거의 100 %가 될 것입니다. Cuckoo 해싱을 기반으로하는 Cuckoo 필터는 삽입이 실제로 실패 할 수있는 용량을 보유합니다. 임의가 아닌 항목 해시를 반복하여 삽입하면 뻐꾸기 필터의 삽입이 실패 할 수 있습니다.

• 속도. 이것은 주관적이며 하드웨어에 많이 의존하지만, 뻐꾸기 필터는 일반적으로 평균적으로 더 빠릅니다 (경험상). 대부분의 블룸 필터 디자인은 해시 함수를 두 번 실행합니다. 특히 보안 해시 함수를 사용할 때 삽입 된 항목을 한 번 해시하는 Cuckoo 필터와 비교할 때 큰 장애가 될 수 있습니다. 내가 본 코드는 Bloom 및 Cuckoo 필터에 다양한 해싱 함수를 사용합니다. Google의 Guava Bloom은 Murmur3을 사용하며 다른 많은 구현에서는 SHA1 또는 다른 것을 사용합니다. 케이스를 사용하기 위해 해시 충돌을 악용 할 수있는 경우 라이브러리가 보안 해시를 사용하는지 확인하십시오. 중요하게 알고있는 것은 Bloom 필터는 삽입하는 데 대략 일정한 시간이 걸리는 반면 Cuckoo 필터는 일정 시간 평균의 경우입니다. 뻐꾸기 필터는 용량의 몇 퍼센트 이내에서 들어가기 때문에 인서트 속도가 크게 느려집니다.그렇더라도 삽입 속도 만 느려지고 다른 모든 작업은 일정한 평균 시간입니다.

• 유연성. 블룸 필터는 삽입 및 포함을 지원합니다. 뻐꾸기 필터는 추가적으로 삭제 및 제한된 카운팅을 지원합니다. 참조 디자인에서 Cuckoo 필터는 항목이 몇 번 삽입되었는지, 최대 7 번까지 결정할 수 있습니다. 블룸 필터는 yes-no 만 결정할 수 있습니다. 뻐꾸기 필터는 또한 삽입 된 항목을 삭제하는 것을 지원합니다. 이는 Bloom에 비해 많은 사용 사례에서 매우 긍정적입니다. 블룸 필터를 사용할 때는 오래된 항목을 삭제할 수 없으므로 "가득 참"(추정 오 탐지율이 임계 값을 초과) 할 때 필터를 처음부터 다시 만드는 것이 좋습니다. 삽입이 실패하기 시작하면 Cuckoo 필터를 사용하여 필터를 다시 작성하므로 유스 케이스에 따라 문제가 될 수 있습니다. 특정 상황에서 Cuckoo 필터는 재 작성하는 대신 필터 제한 내에 머물러있는 항목을 삭제할 수 있으므로 더 유용합니다.

• 지원. 뻐꾸기 필터는 새롭고 많은 언어에 대한 안정적인 라이브러리가 존재하지 않습니다.

블룸 필터의 가장 큰 장점은 대부분의 언어에서 더 성숙한 라이브러리를 지원한다는 것입니다. 블룸 필터의 수학은 과학자들에게 더 잘 이해됩니다. Cuckoo 필터의 대부분의 특성은 경험적으로 결정되었지만 Bloom 필터는 견고한 수치 기반을 가지고 있습니다. 실험적 증거에 따르면 뻐꾸기 필터가 대부분의 환경에서 더 나은 성능을 보여 주지만 성능에 대한 확인이 필요한 실시간 및 중요 시스템 용 뻐꾹 필터는 제외됩니다.

뻔뻔한 플러그 : 저는 자바 용 뻐꾸기 필터 라이브러리의 개발자입니다. . 종이에 사용 된 양동이 반 정렬이 누락되어 공간 효율성이 기준 구현보다 다소 낮습니다. 프로젝트 readme에는 내가 알고있는 다른 구현에 대한 링크가 있습니다. 어떤 구조가 더 나은지는 유스 케이스에 달려 있지만, 주로 솔리드 뻐꾸기 필터 구현이 언어에 적합한 지 여부에 달려있다.

프로덕션 환경에서 Cuckoo/Bloom 필터를 사용하려면 먼저 소스를 살펴 봐야합니다. 내 자신의 글을 쓰기 전에 다양한 libs를 읽었는데 ... 32 비트 기본 배열이나 명백한 성능 문제로 인해 많은 크기 제한이있었습니다. 대부분은 제로 테스트를 받았다. Google의 구아바 블룸 구현에는 최고의 코드 품질과 테스트가 있었으며 (64 비트 배열 제한 지원) 구아바 블룸의 유일한 단점은 보안 해시 기능을 사용할 수있는 옵션이없고 멀티 스레드가 아니라는 것입니다.

프로덕션 시스템에서는 속도를 높이기 위해 멀티 스레딩을 원할 수 있습니다. 구아바 블룸 (Guava Bloom)에 대한 대답은 각 스레드마다 다른 필터를 만들어 가끔씩 결합하는 것입니다. Cuckoo 필터를 결합 할 수 없기 때문에, 나는 Cuckoo 필터 라이브러리에 동시 스레딩을 추가했습니다. 다른 하나는 스레드 안전하지 않거나 동시 적이라는 것을 알고 있습니다.