Proposal: Add DDSketch (Relative-Error Quantile Sketch)

[geonove]

Proposal: Add DDSketch (Relative-Error Quantile Sketch)

Summary:
This issue proposes adding an implementation of DDSketch, a mergeable quantile sketch with relative-error guarantees, to the datasketches-cpp library.

Benefits:

• Relative-error guarantees
• Mergeability for distributed processing
• Predictable memory usage
• Used in production (Datadog, OpenTelemetry)

References

• VLDB 2019: DDSketch Paper
• Datadog's sketches-java repo

Proposed Design

• New class under ddsketch.hpp
• Logarithmic mapping of input values to buckets using configurable relative accuracy
• Compact, bounded memory footprint with optional bucket collapsing
• Mergeable histogram-style structure
• Serialization and deserialization support
• Unit tests and benchmarks included

Compatibility

• No changes to existing APIs
• Implementation will be self-contained
• Optional: initial release could be marked experimental

Next Steps

If there is community interest, I’m happy to:

1. Share a detailed design document
2. Begin work on the implementation and submit a PR
3. Iterate based on feedback

Would the maintainers be open to including DDSketch? Are there specific design or compatibility considerations I should address before proceeding?

[AlexanderSaydakov]

Current quantile sketches in datasketches-cpp (KLL, REQ, t-digest) offer absolute-error guarantees

REQ sketch offers relative error guarantee.

[AlexanderSaydakov]

t-digest also prioritizes high and low rank accuracy
see #416

[AlexanderSaydakov]

I also found this discussion some years ago:
apache/datasketches-java#357

[geonove]

Thank you for the responses and the helpful references to prior discussions @AlexanderSaydakov — this has been very informative.
I’m still interested in exploring a DDSketch implementation, even if just as an experimental project.

Based on the discussion you mentioned, I’ll reflect deeply on whether (and how) it might be possible to make somewhat fair comparisons between sketches with different goals and guarantees.

Please let me know if there could still be interest in this kind of work, or if there’s openness to reopening the discussion at some point down the line.

[AlexanderSaydakov]

Of course, any new sketches are welcome if they have solid research behind them and have substantially different trade-offs compared to ones already implemented in the library. As I understand, closest competitors to DDSketch are REQ sketch and t-digest. Do you think that DDSketch can be a better choice for some applications?

[jmalkin]

I believe it offers accuracy guarantees that t-digest cannot, while providing dual-tailed relative error. It’s numeric so it can do things REQ can’t (two-sided) and is likely smaller, too.

I think it’s a reasonable sketch to include. But we’d want to ensure the API uses similar naming as our existing sketches.

[geonove]

I’ve been working on the characterization of DDSketch and comparing it against t-digest and REQ sketch. After digging into the literature and implementations, one compelling reason to consider adding DDSketch to the library is that it provides accuracy guarantees that the others do not. Specifically, DDSketch guarantees bounded relative error in value space. In contrast, REQ sketch provides guarantees in relative rank error, and t-digest has no formal worst-case bounds.

The figure below shows the relative quantile error as a function of stream size for the three sketches:

Since REQ sketch seems to outperform DDSketch for sufficiently large streams, I'd like to compare their memory footprints as well, to get a full picture. The memory profiling job takes a while to run (hours or maybe days), even after the optimization I did. Does anyone have the data used to produce the memory plots? They don't seem to be in the datasketches-characterization repo.

[leerho]

My criticism off this plot is that the input data is an exponential series, which is the ideal case for the DDSketch because its bins form an exponential series in size. The TDigest, REQ and KLL sketches are much more distribution insensitive. Try some different input distributions.

Also you measurement of error is |true - estimate| / estimate, which is incorrect. It should be (estimate - true) / true. For example: if true = 100 and est = 50, your calculation yields 100%, while the correct calculation is 50% error. Also, It is better to use parenthesis instead of absolute values, as it will inform negative error (underestimates) vs positive error (over estimates).