Prev: [HACKERS] Bloom filters bloom filters
Next: Streaming replication, and walsender during recovery
From: Greg Stark on 18 Jan 2010 08:23
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

--
Sent via pgsql-hackers mailing list (pgsql-hackers(a)postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

 | 
Pages: 1
Prev: [HACKERS] Bloom filters bloom filters
Next: Streaming replication, and walsender during recovery