Обсуждение: Bloom filters bloom filters bloom filters
Another idea of how to make use of bloom filters: It should be possible to implement a gist opclass over a bloomfilter data type which implements the operation int membership in int[]. All you need is a function which takes an int[] and returns a bloom filter. Then your union operation is to just bitwise or the two bloom filters. Your penalty function would be the number of bits required to set in the filter which aren't already set. You could even construct different size bloom filters depending on how large the original set is. When you union two different size filters you need to expand the smaller ones before doing the union but that's an easy operation. I recall gist has a compression function already for storing signatures of large data types for lossy indexing. Have I just described how that works already? I don't recall seeing anything like this in there currently. -- greg
> Then your union operation is to just bitwise or the two bloom filters.
Keep in mind that when performing this sort of union between two comparably-sized sets, your false-positive rate will increase by about an order of magnitude. You need to size your bloom filters accordingly, or perform the union differently. Intersections, however, behave well.
There is a similar problem, among others, with expanding smaller filters to match larger ones.
David Hudson
Keep in mind that when performing this sort of union between two comparably-sized sets, your false-positive rate will increase by about an order of magnitude. You need to size your bloom filters accordingly, or perform the union differently. Intersections, however, behave well.
There is a similar problem, among others, with expanding smaller filters to match larger ones.
David Hudson