30 ms·

FYI, already in 2015, I have proposed exactly the same idea as improvement to HdrHistogram. See https://github.com/HdrHistogram/HdrHistogram/issues/54 https://g

by oertl 7y ago

FYI, already in 2015, I have proposed exactly the same idea as improvement to HdrHistogram. See https://github.com/HdrHistogram/HdrHistogram/issues/54 https://github.com/HdrHistogram/HdrHistogram/issues/54 and corresponding code https://github.com/oertl/HdrHistogram/blob/memory_efficiency/src/main/java/org/HdrHistogram/MemoryEfficientHistogram.java https://github.com/oertl/HdrHistogram/blob/memory_efficiency.... Unfortuantely, the author of HdrHistogram did not pick up my proposal as that would have lead to major changes and problems regarding compatibility. The mapping to histogram bins is the same as in your code https://github.com/DataDog/sketches-java/blob/master/src/main/java/com/datadoghq/sketch/ddsketch/mapping/QuadraticallyInterpolatedMapping.java https://github.com/DataDog/sketches-java/blob/master/src/mai.... I am curious, have you been inspired by that?

CharlesMasson 7y ago
I did see that thread and that's what inspired the mapping with the quadratic interpolation. To clarify though, DDSketch as defined in the paper uses the logarithmic mapping, as our main goal was to make the memory footprint as small as possible. See: https://github.com/DataDog/sketches-java/blob/1650d939f1485f4521f471c48a5d3dd8780ffb16/src/main/java/com/datadoghq/sketch/ddsketch/DDSketch.java#L368:L373 https://github.com/DataDog/sketches-java/blob/1650d939f1485f... The Java implementation abstracts out the index mapping. This let us add alternative ways to map values to indices and we added the method with the quadratic interpolation as it seems to be a good tradeoff between index computation speed and memory footprint.
jamesblonde 7y ago
This sucks, but a problem we have in academia is that you can't reference a closed PR request at a top-tier conference like VLDB. If you wrote up your proposal as a referable document, you should rightly claim that you deserve scholarly recognition. Morally, you deserve recognition (which you are getting here, at least). It's decent of the author to admit he was inspired by you - there are others who would think it is easier to deny it. But there is no recourse, if it's only a PR.

by oertl 7y ago

CharlesMasson 7y ago

I did see that thread and that's what inspired the mapping with the quadratic interpolation. To clarify though, DDSketch as defined in the paper uses the logarithmic mapping, as our main goal was to make the memory footprint as small as possible. See: https://github.com/DataDog/sketches-java/blob/1650d939f1485f4521f471c48a5d3dd8780ffb16/src/main/java/com/datadoghq/sketch/ddsketch/DDSketch.java#L368:L373 https://github.com/DataDog/sketches-java/blob/1650d939f1485f... The Java implementation abstracts out the index mapping. This let us add alternative ways to map values to indices and we added the method with the quadratic interpolation as it seems to be a good tradeoff between index computation speed and memory footprint.

jamesblonde 7y ago

This sucks, but a problem we have in academia is that you can't reference a closed PR request at a top-tier conference like VLDB. If you wrote up your proposal as a referable document, you should rightly claim that you deserve scholarly recognition. Morally, you deserve recognition (which you are getting here, at least). It's decent of the author to admit he was inspired by you - there are others who would think it is easier to deny it. But there is no recourse, if it's only a PR.