leerho commented on PR #772:
URL:
https://github.com/apache/datasketches-java/pull/772#issuecomment-5880197831
@tisonkun,
Very fair questions.
## Question 1: What concrete problem does zeroing the seed hash solve?
### Definitions
* A _hashSeed_ Is a confusing name and should just be called _seed_. It is
a constant that configures a Hash-Function $hash = f(value, seed)$, to return a
deterministic, pseudorandom, (64 or 128bit) _hash_ that is unique to the
_value_ and the _seed_. Once a user selects a _seed_ it should almost never be
changed.
  Inside large organizations, different departments may want to choose
different seeds to prevent accidental merging of sketches. This is not
cryptographic security by any means, since the hash functions themselves are
not cryptographic.
* The CountMinSketch declares a "_private final long[] hashSeeds__",
which is very confusing and should have been just a long array of _seeds__ .
* The BloomFilter declares a single long seed like this:
"_private final long seed_; // hash seed_".
This is marginally OK. The two separated words in the comment imply
"_seed for the hash function_". Given all the confusion around these words I
would prefer the longer phrase for the comment instead.
* A _seedHash_ is the result of applying the same Hash-Function to the
_seed_ itself and is trimmed to 16 bits: $seedHash = (short)hash = f(seed,
seed)$.
* The _seedHash_ is only relevant to **serialized** sketches. And only
used in Theta, Tuple, CPC, CountMin Sketches.
* The reason it was introduced in Theta/Tuple (about 12 years ago), was
to warn the user if an incoming serialized sketch was generated using a
different _seed_ than the user's choice of seed. This assumes the same hash
function, of course, and for all of our sketches that use hash functions, the
hash function is hard wired for a lot of reasons, but a different topic.
* The use of seedHash is a bit strange in the CountMinSketch. It could
have been incorporated into the first preamble long, but instead it is in the
second long. This sketch is quite new and has not had the scrutiny of the
Theta/Tuple/CPC sketches.
### Architectural Concepts and the Theta Sketch
#### Big Data tends to be power-law distributed
It is also important to understand that big data tends to be power-law
distributed. This means that when analyzing massive data it is very likely to
have many millions of empty streams (sometimes null), 100s of thousands of
single item streams, and so on down to very few streams of millions of items.
#### The Theta Sketch is Big
The Theta Sketch is a big sketch compared to HLL (about 8x to 16x bigger).
#### Throughput is inversely related to serialized size
This becomes very evident when processing millions of sketches. As a result
we designed the serialized formats to only contain the required preamble
elements, and focus on the smallest of these formats to be as fast as possible
to process. You can observe this when you look at the documentation in the Java
Theta PreambleUtil class. There are seven different serialization formats for
the Theta sketch.
In particular look at these 4 formats for serialized Compact Theta Sketches:
| Sketch Type | Comment |
|--------|-----------|
| Empty | No: SeedHash, Theta, #Entries, p |
| Single Item, Empty | No: Theta, #Entries, p |
| Exact | No Theta |
| Estimating | Full Preamble |
The serialized, empty CompactThetaSketch has no hashes so it doesn't need a
SeedHash. This 8-byte sketch can be represented as a _static final long_
constant, which makes it extremely fast to detect and process (and the same
size as a null value in a 64bit, >32GB JVM).
### What concrete problem does zeroing the seedHash solve?
1. **Speed.** Making the empty sketch independent of the chosen seed allows
it to be a constant, thus very fast.
2. **Cross-Language Binary (CLB) Testing.** We have already standardized on
the hash function, the default seed value, and default ordered hash array.
Standardizing on the empty sketch format was the last remaining hurdle to
achieve full binary compatibility.
## Question 2: Why does this apply specifically to Theta/Tuple/CPC?
Part of this is history. The Theta/Tuple families were the very first
sketches and we had a lot of focus on throughput. CPC came a little later but
was also a unique counting sketch and sort of a blend of HLL and Theta. When
compressed and serialized was also very small so we felt focusing on its speed
and size performance made sense, and it had similar hash seed compatibility
issues as Theta. Nonetheless, its consistency with our improving
standardization across the library is lacking and could be improved.
The Theta and HLL sketches are just the first of the deterministic sketches
I have looked at for the CLB property, which should evolve to the other
deterministic sketches as well.
The other sketches came much later and had different kinds of hash issues
and trade-offs. The CountMin and Bloom are relatively new and were initially
contributed from the outside, and frankly have not had the same level of
attention paid to consistency with other sketches in the library. In that
regard they can be improved quite a bit.
--
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.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
