You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by "geonove (via GitHub)" <gi...@apache.org> on 2025/05/29 12:27:34 UTC
[I] ## Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
geonove opened a new issue, #457:
URL: https://github.com/apache/datasketches-cpp/issues/457
## Proposal: Add DDSketch (Relative-Error Quantile Sketch)
**Summary:**
This issue proposes adding an implementation of [DDSketch](https://www.vldb.org/pvldb/vol12/p2195-masson.pdf), a mergeable quantile sketch with relative-error guarantees, to the `datasketches-cpp` library.
## Motivation
Current quantile sketches in `datasketches-cpp` (KLL, REQ, t-digest) offer absolute-error guarantees. DDSketch fills a different use case: relative-error quantiles, which are more appropriate for latency percentiles and metrics with a wide dynamic range.
Benefits:
- Relative-error guarantees
- Mergeability for distributed processing
- Predictable memory usage
- Used in production (Datadog, OpenTelemetry)
## References
- VLDB 2019: [DDSketch Paper](https://www.vldb.org/pvldb/vol12/p2195-masson.pdf)
- [Datadog's sketches-java repo](https://github.com/DataDog/sketches-java)
## 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?
Thanks,
Andrea Novellini (@geonove)
--
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: commits-unsubscribe@datasketches.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin commented on issue #457:
URL: https://github.com/apache/datasketches-cpp/issues/457#issuecomment-2920873471
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.
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #457:
URL: https://github.com/apache/datasketches-cpp/issues/457#issuecomment-2920616788
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?
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #457:
URL: https://github.com/apache/datasketches-cpp/issues/457#issuecomment-5924862383
I am going to close this Issue. The associated PR #466 hasn't had any action for a while and has a number of issues that were never resolved. This can always be reopened.
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #457:
URL: https://github.com/apache/datasketches-cpp/issues/457#issuecomment-2920352831
t-digest also prioritizes high and low rank accuracy
see https://github.com/apache/datasketches-cpp/issues/416
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #457:
URL: https://github.com/apache/datasketches-cpp/issues/457#issuecomment-4114271802
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).
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "geonove (via GitHub)" <gi...@apache.org>.
geonove commented on issue #457:
URL: https://github.com/apache/datasketches-cpp/issues/457#issuecomment-2920594311
Thank you for the responses and the helpful references to prior discussions — 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.
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho closed issue #457: Proposal: Add DDSketch (Relative-Error Quantile Sketch)
URL: https://github.com/apache/datasketches-cpp/issues/457
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #457:
URL: https://github.com/apache/datasketches-cpp/issues/457#issuecomment-2920428517
I also found this discussion some years ago:
https://github.com/apache/datasketches-java/issues/357
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #457:
URL: https://github.com/apache/datasketches-cpp/issues/457#issuecomment-2920334475
| Current quantile sketches in datasketches-cpp (KLL, REQ, t-digest) offer absolute-error guarantees
REQ sketch offers relative error guarantee.
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Proposal: Add DDSketch (Relative-Error Quantile Sketch) [datasketches-cpp]
Posted by "geonove (via GitHub)" <gi...@apache.org>.
geonove commented on issue #457:
URL: https://github.com/apache/datasketches-cpp/issues/457#issuecomment-3757012342
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:
<img width="2494" height="1292" alt="Image" src="https://github.com/user-attachments/assets/f0a526d7-9321-4b46-8d41-2eb9ca261da6" />
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](https://github.com/apache/datasketches-characterization/pull/95) I did. Does anyone have the data used to produce the [memory plots](https://private-user-images.githubusercontent.com/13126686/311932751-8cd63172-4524-4e1b-a84c-0efc127fd6be.png?jwt=eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzI1NiJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3Njg1MTM0NTYsIm5iZiI6MTc2ODUxMzE1NiwicGF0aCI6Ii8xMzEyNjY4Ni8zMTE5MzI3NTEtOGNkNjMxNzItNDUyNC00ZTFiLWE4NGMtMGVmYzEyN2ZkNmJlLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNjAxMTUlMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjYwMTE1VDIxMzkxNlomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbm
F0dXJlPTM5ZThhMjlkZTVmZmM2YTlhOWI3ZDQ5OGY3ZDZjMTg2MWIwZjRjNjA4MGU2ZmUyNWY1YTE3NjE2ZGY0Y2IyN2QmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0In0.JnCkGVIk0I0Ajzl0TYGEw4s6cSszDuIS-Aa9msUaMb0)? I didn’t see them in the `datasketches-characterization` repo.
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org