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 bloomfilters.
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
Import Notes
Resolved by subject fallback