Is it possible to estimate the max byte size of a kll sketch? about datasketches-cpp HOT 9 CLOSED

Yes there is. Once a KLL sketch reaches a certain size it grows very slowly, but it does grow. We have provided the function getMaxSerializedSizeBytes(k, n) for exactly this purpose. The only catch is you need to estimate the largest n that you anticipate. If you plot this static function you will discover that for large enough n, it only grows by 32 bytes for every factor of 2 increase in n. So overestimating n by a factor of 2 or 10 won't impact the overall size that much.

from datasketches-cpp.

Oops! I was thinking about the function in the Java version. That function must have been omitted by mistake in the C++ version. We will correct that pronto! :)

from datasketches-cpp.

Thanks @leerho I'll make sure to close this once the function is merged, for now I'll just use my own based on the Java version.

For future reference the relevant Java functions are getMaxSerializedBytes and getSerializedSizeBytes.

from datasketches-cpp.

It was not a mistake to omit getMaxSerializedSizeBytes(k, n) in the C++ implementation, but rather a result of an incomplete process of reconsidering the interface in light of generic implementation.

In Java, KllFloatsSketch is a specialized implementation using a primitive array of floats. There is no generic implementation of KllSketch<T> (yet), and we were not inclined to provide one since the ItemsSketch<T> exists, and the main point of the new KLL sketch was compactness.

In C++, kll_sketch is a template (not optimized for non-fixed sizes yet making potentially avoidable copies of objects). We were not sure what to do with the methods, which provide the serialized size before the serialization is done. They would work for fixed-size types, but not for a generic case of arbitrary custom objects. We need to think about it more and decide whether to have such methods at all, and if so, how to do that better.

from datasketches-cpp.

Thanks for the clarification @AlexanderSaydakov. Would you consider having specialized code paths for fixed-size data types?

I saw references of non-fixed data types in the code, could you provide an example where we might have a non-static size data type that works with kll_sketch? I was not aware of any scalar data types that allocate their own memory.

from datasketches-cpp.

The only requirement for a kll_sketch is that the items be comparable, not that they be primitives. So you're correct with scalar types, but the sketch isn't limited to those and we've generally tried to avoid precluding these sketches from being used in novel ways.

Strings have a variable size, or one could imagine (certainly a contrived example) a sketch of, say, images where they're compared on compressed size but where it stores the images, too. Then you could query to see what images look like at different percentiles in case you want to see what things compress better than others.

Those might not be useful ideas, but it's possible to do them!

from datasketches-cpp.

I implemented get_max_serialized_size_bytes(k, n) for fixed-size types.
I mentioned in the comments that it may not make sense if sizeof(T) is not the same as serialized size of an item, and may need to be specialized (or just not used)

from datasketches-cpp.

could you provide an example where we might have a non-static size data type that works with kll_sketch?

There is a toy example of serialization of kll_sketch<std::string> In kll_sketch_test.cpp

Note that the KLL algorithm does not assume numeric types. The only requirement is to define the order (operator<) between the items.

from datasketches-cpp.

Closed by 1770317

from datasketches-cpp.