On Tue, Mar 17, 2020 at 12:28 AM Alex Herbert <alex.d.herb...@gmail.com>
wrote:
>
> > The Shape tells the hasher how many hash functions to apply to each item.
>
> OK. This is may misunderstanding. There is a contract that the Hasher is
> expected to fulfil but it is just not recorded in the javadoc. I can update
> the docs to indicate that:
>
> "A Hasher represents items of arbitrary byte size as a byte representation
> of fixed size (a hash). The hash for each item is created using a hash
> function; use of different seeds allows generation of different hashes for
> the same item. The hashes can be dynamically converted into the bit index
> representation used by a Bloom filter. The shape of the Bloom filter
> defines the number of indexes per item and the range of the indexes. The
> hasher functions to generate the correct number of indexes in the range
> required by the Bloom filter for each item it represents.
>
> Note that the process of generating hashes and mapping them to a Bloom
> filter shape may create duplicate indexes. The hasher may generate fewer
> than the required number of hash functions per item if duplicates have been
> removed."
>
> Looks Good
> > The Shape number of items is how many items are expected to be in the
> final
> > Bloom filter, it is more the expected value not a hard limit.
>
> Yes. As discussed before this is not actually required for a Bloom filter
> to function, it is required to maintain the intended purpose of the filter
> when it was constructed.
>
>
>
> >
> > The static hasher for example will not return duplicates so it might
> appear
> > that it has not respected the number of functions. In addition there is
> no
> > indication from the hasher how many items it contains..
>
> Yes. So we state that the hasher represents one or more items.
>
> >
> > The inputs to the hash.builder are byte buffers that are fed to the hash
> > algorithm. They are inputs to that algorithm. So primitive types would
> > simply convert from the primitive type to its byte buffer representation.
> > Is that what you meant?
>
> I was unclear on the purpose of the Hasher.Builder. It seemed incomplete.
> If the builder is to add items then it seems strange to have:
>
> with(byte property)
> with(String property)
>
> It also seems strange to throw 'IllegalStateException if the Hasher is
> locked’ without explaining what this means. Is the builder intended to be
> concurrent? What is ‘locked’? Etc.
>
Good catch. Documentation error. Originally the Hasher.Builder was locked
once it generated a Hasher that was removed but the documentation was not
cleaned up.
> The byte could not possibly represent many meaningful objects. The string
> is trivially converted to UTF-8 bytes (as is done in the DynamicHasher).
> Both these methods could be added to the interface as default methods or
> preferrably dropped as they are so trivial.
>
> I changed the documentation to remove the encoding as UTF-8 requirement
> from the with(String) method. It seems like an implementation detail and a
> Hasher.Builder implementation can decide how to convert the String. It is
> faster to use UTF-16 bytes for instance. I understand UTF-8 is for
> cross-platform standard. But mandating that it has to be done is too
> restrictive IMO. It would be better as:
>
> with(CharSequence, Charset)
> withUnencoded(CharSequence)
>
>
The Hasher.Builder is patterned after the cryptography MessageDigest
pattern where a number of update() calls are made before a final digest()
produces the hash. Originally it was update() and build() but earlier
suggestion was to change the update() to with().
Adding with( byte[] buffer, int offset, int len ) makes sense.
with(String ) is a convenience method, it was documented as UTF-8 so that
if when trying to build equivalent filters in a different language there
was no need to look deep in the hasher code to figure out what to do.
with( byte ) is also a convenience method.
They are documented in Hasher.Builder to be common across all builders.
Obviously different Builder implementations can add other functionality.
One could build a decorator that wraps a builder and adds the with(<T>)
functionality.
The Builder interface is designed to be a balance between minimal
implementation need to be functional and an implementation that can handle
all arbitrary types.
> I was interpreting the Hasher.Builder as a builder of a single byte[] for
> hashing where you would pass different primitive values or byte[] for the
> same Object you want to convert. This is essentially a ByteBuffer. But if
> it is to receive an entire object for each call then (a) it should be
> documented as such; (b) it should be simplified to just the byte[] method
> with perhaps another one/two:
>
> with(byte[])
> with(byte[], int length)
> with(T)
> with(ByteBuffer)
>
> Adding the T method would make the interface typed as Hasher.Builder<T>.
> It would require a function to convert items T to a byte[]:
>
>
I think the T and ByteBuffer implementations are better left to a decorator
class. But that is just my take. Since the Bloom filter only supports a
logical equivalent of equals putting numerical values into a Bloom filter
is not that common. My experience is that most values are Strings.
Collection<T> items = ...
> BloomFilter bf = …
> Function<T, byte[]> converter = …
> HashFunction hf = ...
>
> for (T item : items) {
> bf.merge(new DynamicHasher.Builder<>(hf,
> converter).with(item).build());
> }
>
> Or:
>
> DynamicHasher.Builder<T> builder = new DynamicHasher.Builder<>(hf,
> converter);
> for (T item : Collection<T>) {
> builder.with(item);
> }
> bf.merge(builder.build());
>
> I think the Hasher.Builder interface can be removed. It does not really
> add anything to the API without a factory somewhere to be able to create
> Hasher.Builder instances since each instance has no methods for reset:
>
> At one time Builder.build() performed a reset but that was removed by
request, I would have no issues putting it back, or adding a reset method.
The Hasher.Builder interface defines a common interface across all
builders. So I can write my code to build Bloom filters and swap out the
hasher implementation easily as long as I stick to the Builder.Hasher
methods.
Hasher h = factory.create().with(x).with(y).with(z).build();
>
> If you do not have either a factory to create a Hasher.Builder or the
> ability to reset a Builder then why have a Hasher.Builder interface?
> Passing around just a single instance of the builder has limited use. I
> would drop the interface and leave it to Hasher implementations to define
> how they want to be constructed.
>
> >
> > The hasher contract is that it will generate integers in the proper range
> > and use the proper number of hash functions for each item that was added
> to
> > the builder and that repeated calls to getBits(Shape) will return the
> same
> > values.
> >
> > Did I misunderstand something?
>
> No, I did. Hence the need to clarify all the javadoc.
>
> What I think we are missing with the Hasher is the simplicity of the Guava
> implementation. What you ideally would like to do is:
>
> Collection<T> items = ...
> BloomFilter bf = …
>
> for (T item : items) {
> bf.merge(item);
> }
>
> This change significantly reduces the applicability of this implementation
of Bloom filter across applications. I am currently working on several
applications where Hashers are sent across a network to query repositories.
By separating the Hasher from the Filter (separation of concerns) then I
don't have to send large objects across the network to do the query. Nor
do I have to expose the properties I am querying for. In addition the
endpoints I am querying are free to resize the bloom filters they store as
they see fit based on size of collection and other Shape based concerns.
With the Guava implementation this is not possible.
Note: "properties" in the above paragraph are items placed into a single
builder.
Currently you have to do something like:
>
> Collection<T> items = ...
> BloomFilter bf = …
> Function<T, Hasher> itemToHasher = …
>
> for (T item : items) {
> bf.merge(itemToHasher.apply(item));
> }
>
> The itemToHasher is effectively an improved DynamicHasher.Builder<T> as
> above.
>
Yes, and simple to construct from the components in the bloomfilter
packages. In addition, I think you have made the assumption that T
contains a single value to be added, in which case a Function<T,byte[]>
would suffice and, assuming bf is not a CountingBloom filter, the above can
be written as:
Hasher.Builder builder = new ....
Function<T,byte[]> f = new ...
items.iterator().forEachRemaining( t -> builder.with( f.apply(t) )
bf.merge( builder.build() )
Additionally if T is an object with multiple elements that are to be added
to the filter then
Hasher.Builder nativeBuilder = new ....
DecoratorT builder = new DecoratorT( nativeBuilder ) // adds the with(T)
method
items.iterator().forEachRemaining( t -> builder.with( t ) )
bf.merge( builder.build() )
there is no difference in result between
-
loop {
bf.merge( new Builder().with(x).build() )
}
-- and --
new Builder()
loop {
builder.with( x )
}
bf.merge( builder.build() );
> It would also be possible for the itemToHasher to recycle byte[] space by
> returning the same Hasher object that has been reset and filled with the
> next item. This would not be thread-safe but would save on intermediate
> storage.
>
> All of this still fixes on having a byte[] representation to feed to a
> HashFunction. Moving away from the current design would change HashFunction
> to specify methods to accept blocks of data and have a final method to get
> the hash. So making the HashFunction an online hash. This would then match
> Guava by having the some object accept items T and require a function to
> map the item T to blocks of data.
>
> However I note that the current implementation that accepts a byte[] for
> each call to get a hash value with a different seed can either use the
> byte[] or not (if cyclic). If the HashFunction was online then the choice
> of cyclic or iterative would not easily be possible. The Guava
> implementation creates a single hash and then the BloomFilter always uses
> this with a cyclic method. So the move away from the current design would
> be less flexible to allow different implementations of hashing.
>
> So we keep the byte[] interface to HashFunction for now. A performance
> test can be used to determine if there is an advantage to an advanced
> DynamicHasher.Builder which can recycle byte[] space. Javadoc should be
> added to the HashFunction to indicate that the same bytes passed with the
> same seed should create the same output. The same bytes with a different
> seed should create different output with very high probability. A seed of
> zero is used as a reset signal for implementations that have cached
> computation results that the byte[] input is different from the previous
> call.
>
>
> The last thing is that the Hasher.isEmpty() is not used anywhere except
> the units tests. It seems strange to have it. Can we just assume a Hasher
> is not empty. An empty hasher would return an iterator that does nothing.
>
> Yes, I guess we don't need isEmpty() I think it was originally used in
BloomFilter.merge() in a guard statement to test if the merge actually
needed to attempt to do anything.
> In summary:
>
> 1. change Hasher getBits to iterator
>
agree
> 2. improve documentation of Hasher and the contract that it should fulfil
> with respect to items and a Shape
>
absolutly
> 3. potentially drop Hasher.Builder unless there is a way to reset the
> Builder or create more
>
add the reset or have build() implicitly do a reset.
4. Or make Hasher.Builder typed to an object <T> so it is clear the with(…)
> methods are to accept a full representation of an item and add it to the
> in-progress Hasher currently being built
>
disagree.
5. Improve HashFunction javadoc on the use of the seed as a reset signal
agree
> 6. Drop Hasher.isEmpty()
>
ambivalent.
>
> That should clarify the currently functionality.
>
> Thought on this?
>
> Alex
>
>
> >
> > Claude
> >
> >
> > On Mon, Mar 16, 2020 at 6:34 PM Alex Herbert <alex.d.herb...@gmail.com>
> > wrote:
> >
> >>
> >> On 16/03/2020 07:57, Claude Warren wrote:
> >>> I made a quick pass at changing getHasher() to iterator().
> >>
> >> A look at the feasibility or have you started work on this? If so then
> >> I'll not start work on it as well.
> >>
> >> I changed master to return a boolean for the merge operations in
> >> BloomFilter. So the outstanding changes are to drop getHasher() from the
> >> BloomFilter interface in favour of an iterator, spliterator and a
> >> forEachBit method.
> >>
> >>> I think we can get rid of HasherBloomFilter as its purpose was really
> to
> >>> create a Bloom filter for temporary usage and it doesn't seem to be
> >>> required if we have a hasher that can be created from a Shape and a
> >>> function that creates an Iterator.
> >>
> >> I agree.
> >>
> >> One change that could be made is to clarify the contract between a
> >> Hasher and a BloomFilter. At present the Hasher can operate without a
> >> defined contract in this method:
> >>
> >> PrimitiveIterator.OfInt getBits(Shape shape)
> >>
> >> It should validate that it can generate indexes for the shape. But it
> >> doesn't have to. It could return unlimited indexes and they could be
> >> outside the number of bits of the BloomFilter.
> >>
> >> There does not appear to be any control anywhere on the number of hash
> >> functions generated by the Hasher. I would expect this test in the
> >> AbstractBloomFilterTest to pass:
> >>
> >> @Test
> >> public void hasherMergeTest() {
> >> int n = 1;
> >> int m = 10;
> >> HashFunctionIdentity h = new
> >> HashFunctionIdentityImpl("provider", "name",
> >> Signedness.SIGNED, ProcessType.CYCLIC, 0L);
> >> Hasher hasher = new Hasher() {
> >> @Override
> >> public boolean isEmpty() {
> >> return false;
> >> }
> >> @Override
> >> public HashFunctionIdentity getHashFunctionIdentity() {
> >> return h;
> >> }
> >> @Override
> >> public OfInt getBits(Shape shape) {
> >> // Do not respect the shape number of hash functions
> >> but do respect
> >> // the number of bits
> >> return IntStream.range(0, m).iterator();
> >> }
> >> };
> >> for (int k = 1; k < 5; k++) {
> >> Shape shape = new Shape(h, n, m, k);
> >> BloomFilter bf = createEmptyFilter(shape);
> >> bf.merge(hasher);
> >> assertEquals("incorrect cardinality", k, bf.cardinality());
> >> }
> >> }
> >>
> >> It currently does not as all the BloomFilters will not respect the Shape
> >> with which they were created, i.e. they disregard the number of hash
> >> functions in the Shape. So does the Hasher.
> >>
> >> I think some of the control should be returned to the BloomFilter. The
> >> Hasher would be reduced to a simple generator of data for the
> >> BloomFilter, for example:
> >>
> >> PrimitiveIterator.OfInt getBits(int m);
> >> PrimitiveIterator.OfInt getBits(int k, int m);
> >> PrimitiveIterator.OfLong getBits();
> >>
> >> The BloomFilter then accept responsibility for converting the primitives
> >> to a suitable index and creating the correct number of hash functions
> >> (i.e. indexes).
> >>
> >> A merge operation with a BloomFilter then becomes:
> >>
> >> - check the Hasher is using the correct hash function identity
> >> - ask the Hasher for an iterator
> >> - set k bits in the filter using the iterator, mapping each to the range
> >> [0, m)
> >>
> >> The BloomFilter has then encapsulated its state and respects the Shape.
> >>
> >> The HashFuntion will convert byte[] to a long.
> >>
> >> The Hasher exists to convert anything to a byte[] format.
> >>
> >> This perhaps needs the Hasher.Builder to be revised to include more
> >> methods that accept all the primitive data types. These are all
> >> converted to a single byte[] representation. Thus the Hasher.Builder is
> >> effectively a specification for a ByteBuffer. Once an object is
> >> decomposed into the byte[] it can be fed through the HashFunction with
> >> different seeds or using the cyclic method to create the iterator. The
> >> BloomFilter consumes the raw long output from the stream produced by the
> >> Hasher and sets k bits within the range m.
> >>
> >> Alex
> >>
> >>
> >>
> >> ---------------------------------------------------------------------
> >> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> >> For additional commands, e-mail: dev-h...@commons.apache.org
> >>
> >>
> >
> > --
> > I like: Like Like - The likeliest place on the web
> > <http://like-like.xenei.com>
> > LinkedIn: http://www.linkedin.com/in/claudewarren
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>
--
I like: Like Like - The likeliest place on the web
<http://like-like.xenei.com>
LinkedIn: http://www.linkedin.com/in/claudewarren
