Claudenw commented on issue #83: Initial bloom filter code contribution URL: https://github.com/apache/commons-collections/pull/83#issuecomment-573396667 > ## HashFunctionIdentity > > I thought it was an identity as seen in some functional programming libs/ > code. As when f(x) = x, f(1) = 1, etc. But looks like it's actually the > base class of a hash function. I can see how this name has a logical semantic conflict. Do you have a better name? I am open to renaming it. > ## Filters ... > I tried creating a similar example with our Collections version, but I > think I may have misunderstood something and created an example too > verbose? > > ```java > package org.apache.commons.collections4.bloomfilter; > > import org.apache.commons.collections4.bloomfilter.hasher.DynamicHasher; > import org.apache.commons.collections4.bloomfilter.hasher.function.MD5Cyclic; > > public class TT { > > public static void main(String[] args) { > BloomFilter.Shape shape = new BloomFilter.Shape( new MD5Cyclic(), 1, Integer.MAX_VALUE, 1 ); > DynamicHasher.Builder builder = new DynamicHasher.Builder( new MD5Cyclic()); > DynamicHasher hasher = builder > .with("banana".getBytes()) > .with("apple".getBytes()) > .with("pear".getBytes()) > .build(); > BloomFilter collectionsBloomFilter = new BitSetBloomFilter(hasher, shape); > System.out.println(collectionsBloomFilter.cardinality()); > System.out.println( > collectionsBloomFilter.contains(builder.with("banana".getBytes()).build()) > ); > System.out.println( > collectionsBloomFilter.contains(builder.with("apple".getBytes()).build()) > ); > System.out.println( > collectionsBloomFilter.contains(builder.with("pear".getBytes()).build()) > ); > System.out.println( > collectionsBloomFilter.contains(builder.with("pineapple".getBytes()).build()) > ); > // this doesn't work, and returns just false > System.out.println( > collectionsBloomFilter.contains(builder > .with("banana".getBytes()) > .with("pear".getBytes()) > .with("apple".getBytes()) > .with("pineapple".getBytes()).build()) > ); > // 3 > // true > // true > // true > // false > // false > } > } > ``` > > So given I want to index Strings with a bloom filter, and I won't know > the strings that I want to index, I assume I need a DynamicHasher? Or > if I knew the possible strings, then I could create a StaticHasher (right?). You are correct in that the dynamic hasher is the only implementation that will build from strings. The StaticHasher is used when you know the bits you want to turn on and don't have the hash. It is included here for two reasons: 1. There was a request for the ability to check a bloom filter without having to build another representation in memory where the bloom filter bits were known. 2. It provides a mechanism to convert from one implementation of `BloomFilter` to another. > > However, in order to create a filter, I need to tell it what is the > Shape of the object I want to index. The Shape may need other arguments > like hasher function, probabilities, elements size, etc. Yes you need to tell the filter what shape it is. This is effectively what the Hadoop system does in: `new BloomFilter(1_000, 7, Hash.MURMUR_HASH);` Shape is not the shape of the object to index but the shape of the resulting Bloom filter. > And I may need a hasher too, or use the implementation default hasher > (BitSetBloomFilter uses a StaticHasher). You need a hasher. In the Hadoop system the hasher is built into the BloomFilter. Here it is separated. Merging the Hasher into the BloomFilter is possible and the Hadoop Bloom filter could be implemented with the Commons Bloom filter library. However, keeping them separate allows an architecture where a client constructs a hasher and passes that to remote systems for query. That implementation of `Hasher` is not here but I will contribute it. I was planning on making it an addition after we got the base code in. If you think it should go now I am happy to add it. The code is at https://github.com/Claudenw/MultidimentionalBloom/blob/master/src/main/java/org/xenei/bloom/filter/CachingHasher.java > Then if I want to check if a String (e.g. URL) exists with the filter, > I actually need a hasher or another filter? Isn't there a simpler way > to create a filter more quickly, with more defaults, perhaps? The short answer is yes, there is a simpler way. The long answer is that to make it simpler one would have to crate a class that merges the Hasher into the Bloom filter. Perhaps it would make sense to create a `SimpleBloomFilter` that merges the `DynamicHasher` and the `BitSetBloomFilter` and provides methods like the Hadoop Bloom filter. The reason the Hasher and the Filter are different classes is a separation of responsibility. Conceptually the Hasher does as it says and converts buffers of bytes into an iterator of `int` (the indexes of the bits to turn on in the filter). The StaticHasher simply replays an earlier hashing. The Filter is responsible for the representation of the enabled bits. The three choices provided in this contribution are: BitSet , Counting, xor Hasher based. (The Hasher based calls the underlying hasher repeatedly so is the slowest, but least memory hungry). In most cases the BitSet implementation will be sufficient. However, for very large filters where the number of bits is large and the number of functions is small (e.g bioinformatics k-mer searches) the number of off bits significantly outweigh the number of on bits and other representations become much more efficient. So the Filter implementation selection is dependent upon the use case. The separation of responsibility makes implementation of specialized Bloom filters like multidimensional, attenuated, and spectral possible with this library. > > Sorry if I misunderstood how it should be used. I tried using the unit > tests as example but still couldn't come up with a simpler example. Your example was spot on. > > Cheers > Bruno Thank you for your in depth review and comments. I will be addressing the typos and other minor issues today. Claude
---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services
