블룸 필터를 사용하면 어떤 이점이 있습니까?

블룸 필터를 사용하면 어떤 이점이 있습니까?

---

나는 블룸 필터를 읽고 있는데 그들은 단지 어리석은 것처럼 보입니다. 블룸 필터로 수행 할 수있는 모든 작업은 다중이 아닌 단일 해시 함수를 사용하여 더 적은 공간에서 더 효율적으로 수행 할 수 있습니다. 블룸 필터를 사용하는 이유는 무엇이며 어떻게 유용합니까?

---

에서 위키 백과 :

블룸 필터는 자체 균형 이진 검색 트리, 시도, 해시 테이블 또는 간단한 배열 또는 항목의 연결 목록과 같은 집합을 나타내는 다른 데이터 구조에 비해 강력한 공간 이점이 있습니다. 이들 중 대부분은 최소한 데이터 항목 자체를 저장해야합니다. 작은 정수의 경우 작은 비트에서 문자열과 같은 임의의 비트 수까지 어디에서나 필요할 수 있습니다 (시도는 예외입니다. 같은 접두사가있는 요소). 연결된 구조는 포인터에 대한 추가 선형 공간 오버 헤드를 발생시킵니다. 반면에 오류가 1 %이고 최적 값이 k 인 Bloom 필터는 요소의 크기에 관계없이 요소 당 약 9.6 비트 만 필요합니다. 이 이점은 부분적으로는 소형화, 어레이에서 상속되고 부분적으로는 확률 적 특성에서 비롯됩니다.

나에게 꽤 명확합니다.

블룸 필터는 요소 자체를 저장하지 않습니다. 이것이 중요한 포인트입니다. 요소가 있는지 테스트하는 데 블룸 필터를 사용 하지 않고 거짓 부정을 보장하지 않으므로 확실히 존재 하지 않는지 테스트하는 데 사용합니다 . 이렇게하면 집합에 존재하지 않는 요소 (예 : 조회를위한 디스크 IO)에 대해 추가 작업을 수행 할 수 없습니다.

그리고 모두 해시 테이블 (대용량 데이터 세트의 경우 디스크에 부분적으로있을 가능성이 높음)과 같은 것보다 훨씬 적은 공간에 있습니다. 해시 테이블과 같은 구조 와 함께 블룸 필터 를 사용할 수 있지만 일단 요소가 존재할 가능성이 있다고 확신하면.

따라서 예제 사용 패턴은 다음과 같습니다.

디스크에 많은 데이터가 있습니다 . m 값을 규정하는 원하는 오류 범위 (예 : 1 %)를 결정합니다 . 그런 다음 최적의 k 가 결정됩니다 (기사에 제공된 공식에서). 이 디스크 바인딩 데이터에서 필터를 한 번 채 웁니다.

이제 RAM에 필터가 있습니다. 일부 요소를 처리해야하는 경우 필터를 쿼리하여 데이터 세트에 존재할 가능성이 있는지 확인합니다. 그렇지 않은 경우 추가 작업이 수행되지 않습니다. 디스크 읽기 등이 없습니다 (해시 나 트리 등의 경우 수행해야 할 작업).

그렇지 않고 필터에 "예, 거기에 있습니다"라고 표시되면 1 %의 확률로 잘못된 것이므로 알아 내기 위해 필요한 작업을 수행합니다. 시간의 99 %가, 정말 할 일이 수포이 없었다,가.

---

Alex는 그것을 아주 잘 설명했습니다. 아직 이해하지 못한 사람들을 위해이 예제가 다음을 이해하는 데 도움이되기를 바랍니다.

Chrome 팀에서 Google에서 일하고 사용자가 입력 한 URL이 악성 URL 인 경우 사용자에게 알리는 기능을 브라우저에 추가하고 싶다고 가정 해 보겠습니다. 약 1 백만 개의 악성 URL 데이터 세트가 있는데,이 파일의 크기는 약 25MB입니다. 크기가 상당히 크기 때문에 (브라우저 자체의 크기에 비해 큼)이 데이터를 원격 서버에 저장합니다.

사례 1 : 해시 테이블과 함께 해시 함수를 사용합니다. 효율적인 해싱 기능을 결정하고 해시 기능을 통해 100 만 개의 URL을 모두 실행하여 해시 키를 얻습니다. 그런 다음 해시 테이블 (배열)을 만듭니다. 여기서 해시 키는 해당 URL을 배치 할 인덱스를 제공합니다. 이제 해싱 테이블을 해시하고 채우면 크기를 확인합니다. 키와 함께 해시 테이블에 1 백만 개의 URL을 모두 저장했습니다. 따라서 크기는 최소 25MB입니다. 이 해시 테이블은 크기 때문에 원격 서버에 저장됩니다. 사용자가 찾아와 주소창에 URL을 입력하면 악성인지 확인해야합니다. 따라서 해시 기능을 통해 URL을 실행하고 (브라우저 자체가이를 수행 할 수 있음) 해당 URL에 대한 해시 키를 얻습니다. 이제 해시 키를 사용하여 원격 서버에 요청해야합니다. 특정 키가있는 내 해시 테이블의 특정 URL이 사용자가 입력 한 것과 동일한 지 확인합니다. 그렇다면 그것은 악의적이며 그렇지 않다면 그것은 악의적이지 않습니다. 따라서 사용자가 URL을 입력 할 때마다 해당 URL이 악성 URL인지 확인하기 위해 원격 서버에 요청해야합니다. 이것은 많은 시간이 걸리므로 브라우저 속도가 느려집니다.

사례 2 : 나는 블룸 필터를 사용합니다. 1 백만 개의 URL 전체 목록은 여러 해시 함수를 사용하여 블룸 필터를 통해 실행되며 각 위치는 0의 거대한 배열에서 1로 표시됩니다. 블룸 필터 계산기 ( http://hur.st/bloomfilter?n=1000000&p=0.01)를 사용하여 1 %의 오 탐률을 원한다고 가정 해 보겠습니다 .), 필요한 블룸 필터의 크기는 1.13MB에 불과합니다. 이 작은 크기는 배열의 크기가 크더라도 해시 테이블의 경우처럼 URL이 아닌 1 또는 0 만 저장하기 때문에 예상되며이 배열은 비트 배열로 취급 할 수 있습니다. 즉, 1과 0의 두 값만 있기 때문에 바이트 대신 개별 비트를 설정할 수 있습니다. 이렇게하면 차지하는 공간이 8 배 줄어 듭니다. 이 1.13MB 블룸 필터는 크기가 작기 때문에 웹 브라우저 자체에 저장할 수 있습니다 !! 따라서 사용자가 URL을 입력 할 때 필요한 해시 함수 (브라우저 자체에서)를 적용하고 블룸 필터 (브라우저에 저장 됨)의 모든 위치를 확인하기 만하면됩니다. 모든 위치의 값이 0이면이 URL이 악성 URL 목록에 확실히 포함되어 있지 않으며 사용자가 자유롭게 진행할 수 있음을 나타냅니다. 따라서 우리는 서버를 호출하지 않았으므로 시간을 절약했습니다. 값 1은 URL이 악성 URL 목록에있을 수 있음을 나타냅니다. 이 경우 우리는 원격 서버를 호출하고 거기에서 URL이 실제로 존재하는지 검색하고 확인하기 위해 첫 번째 경우에서와 같이 해시 테이블과 함께 다른 해시 함수를 사용할 수 있습니다. 대부분의 경우 URL은 악의적 인 URL이 아닐 가능성이 높으므로 브라우저의 작은 블룸 필터가이를 파악하여 원격 서버에 대한 호출을 피하여 시간을 절약합니다. 경우에 따라 블룸 필터가 URL이 악성 일 수 있다고 알려주는 경우에만 서버를 호출합니다. 그 'MIGHT'이 99 % 맞습니다. 이 경우 우리는 원격 서버를 호출하고 거기에서 URL이 실제로 존재하는지 검색하고 확인하기 위해 첫 번째 경우와 같이 일부 해시 테이블과 함께 다른 해시 함수를 사용할 수 있습니다. 대부분의 경우 URL은 악의적 인 URL이 아닐 가능성이 높으므로 브라우저의 작은 블룸 필터가이를 파악하여 원격 서버에 대한 호출을 피하여 시간을 절약합니다. 경우에 따라 블룸 필터가 URL이 악성 일 수 있다고 알려주는 경우에만 서버를 호출합니다. 그 'MIGHT'이 99 % 맞습니다. 이 경우 우리는 원격 서버를 호출하고 거기에서 URL이 실제로 존재하는지 검색하고 확인하기 위해 첫 번째 경우에서와 같이 해시 테이블과 함께 다른 해시 함수를 사용할 수 있습니다. 대부분의 경우 URL은 악의적 인 URL이 아닐 가능성이 높으므로 브라우저의 작은 블룸 필터가이를 파악하여 원격 서버에 대한 호출을 피하여 시간을 절약합니다. 경우에 따라 블룸 필터가 URL이 악성 일 수 있다고 알려주는 경우에만 서버를 호출합니다. 그 'MIGHT'이 99 % 맞습니다. 브라우저의 스몰 블룸 필터는이를 파악하여 원격 서버에 대한 호출을 피함으로써 시간을 절약합니다. 일부 경우에만 블룸 필터가 URL이 악성 일 수 있다고 알려주는 경우에만 서버를 호출합니다. 그 'MIGHT'이 99 % 맞습니다. 브라우저의 스몰 블룸 필터는이를 파악하여 원격 서버에 대한 호출을 피함으로써 시간을 절약합니다. 경우에 따라 블룸 필터가 URL이 악성 일 수 있다고 알려주는 경우에만 서버를 호출합니다. 그 'MIGHT'이 99 % 맞습니다.

따라서 브라우저에서 작은 블룸 필터를 사용하여 입력 된 모든 URL에 대해 서버 호출을 할 필요가 없기 때문에 많은 시간을 절약했습니다.

단일 해시 함수가있는 해시 테이블이 블룸 필터와는 다른 목적으로 사용되는 것을 볼 수 있습니다. 바라건대 이것은 당신의 의심을 없애줍니다 :)

편집 :

Python에서 악성 URL 테스트 작업을 위해 블룸 필터를 구현했습니다. 코드는 여기에서 찾을 수 있습니다. https://github.com/tarunsharma1/Bloom-Filter 코드는 이해하기 매우 간단하며 readme 파일에 자세한 설명이 제공됩니다.

---

블룸 필터가 무엇인지, 무엇을 할 수 있고 무엇을 할 수 없는지, 왜 필요한지 설명하고, 어떻게 작동하는지 직관적 인 설명을 보여주고, 유용 할 때 몇 가지 예를 들어 보겠습니다.

So a standard bloom filter is a probabilistic data structure that can^*:

---

• add element to a set
• check if an element is in the set by telling definitely not in the set or possibly in the set

This possibly in the set is exactly why it is called probabilistic. Using smart words it means that false positive are possible (there can be cases where it falsely thinks that the element is positive) but false negative are impossible.

But it can't ^*:

• remove an item from the set
• give you a list of all elements that are currently in your set

^*_{This set of can/can't is for a basic bloom filter. Because it is a useful data structure that was created long time ago, people found how to augment it with other useful features.}

---

But wait a minute: we already know a data structure that can answer all of this without vague 'possible' and also without all of the limitations (can't remove, can't show all). And it is called a set. And here comes a main advantage of a bloom filter: it is space efficient and space constant.

This means that it does not matter how many elements do we store there, the space will be the same. Yes a bloom filter with 10^6 elements (useless bloom filter) will take the same amount of space as a bloom filter with 10^20 elements and the same space as bloom filter with 0 elements. So how much space will it take? It is up to you to decide (but there is a trade of: the more elements you have the more uncertain you are with you possible in the set answer.

Another cool thing is that it is space constant. When you save the data to a set, you have to actually save this data. So if you store this long string in the set you have to at least use 27 bytes of space. But for a 1% error and an optimal value of k ^**, you will need ~ 9.6 bits ( < 2 bytes) per any element (whether it is a short int or a huge wall of text).

Another property is that all the operations are taking constant time, which is absolutely not the same as amortized constant time in case of sets (remember that if the set has collisions, it can deteriorate in O(n) time).

^**_{k is a value of hash functions used in the bloom filter}

---

I will not describe how the bloom filters work (wikipedia article does a very good job explaining everything). Here I will just briefly tell the basics.

• you initiate an empty bit array of length m
• you select k different hash functions (the more independent the better)
• if you want to add element, you calculate all the k hashes of this value and set the corresponding bits to 1
• if you want to check if element exist, you also calculate all k hashes and if at least one of them is not set, it is surely is not in the set. Otherwise it can be in the set.

Even this description is enough to understand why we can't be sure (you can get all bits set from various other values). Here is a very nice visualization of how it works.

---

So when can bloom filters be useful? The short answer is everywhere where false positive are acceptable and where you would want to check if something is in the set, but even if they are not, it can be a first line of defense to rule out expensive calls to verifiers.

Here is a list of more concrete descriptions:

• a standard example of malicious websites and a browser is described in almost any place where people talk about bloom filters
• is a passwords weak: instead of having a huge set of all possible weak passwords, you can just check whether the password is surely not weak with a way smaller bloom filter
• if you have a list of articles and a list of users, you can use bloom filter to show users' articles they have not read. Interesting thing is that you can have only one filter (you check whether the combination of user_id + article_id is there)
• bitcoin uses bloom filter for wallet synchronization
• Akamai's web servers use Bloom filters to prevent "one-hit-wonders" from being stored in its disk caches. One-hit-wonders are web objects requested by users just once, something that Akamai found applied to nearly three-quarters of their caching infrastructure. Using a Bloom filter to detect the second request for a web object and caching that object only on its second request prevents one-hit wonders from entering the disk cache, significantly reducing disk workload and increasing disk cache hit rates (taken from examples in bloom's filter article at wiki)

---

Bloom filters are quite useful in bioinformatics. They can be more space efficient compared to using a regular hash, especially when the size of the strings you are working with can be hundreds of millions of letters with a very small alphabet ie {A,G,T,C} . They are usually used to assess whether a certain k-mer is present or absence in a genome. There's an example of one used for something relevant here.

EDIT:

The multiple hash functions are used to minimize false positives. The hope is that between all of the k-hash functions each value will have a unique signature in the bit-array compared to every other possible value. However, false positives do exist, but they can be minimized to a manageable level. Using this technique you hash elements independently of their size. When you search for them, you use each hash function and check to make sure their bit-values are all 1.

Compare this to the human genome, where an increase in the size of the element increases the size of the hash table significantly (The table size is 4*4^k). This is assuming you encode the the elements using 2 bits / letter.

---

If a Bloom filter returns that an item is member of the set, there's a certain probability for a false positive. If only a single hash function were used to indicate membership in the set, the probability of a false positive would be higher than using multiple hash functions.

참고URL : https://stackoverflow.com/questions/4282375/what-is-the-advantage-to-using-bloom-filters