Proposal: Add DDSketch (Relative-Error Quantile Sketch)
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 45/100
Research direction
Start by reading the DDSketch paper and Datadog's sketches-java reference. The proposed implementation belongs in ddsketch.hpp and should include serialization, deserialization, unit tests, and benchmarks. Done means a self-contained, mergeable DDSketch with configurable relative accuracy and bounded memory, without changing existing APIs.
Written by the indexing model from the issue text.
Description
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:
- Share a detailed design document
- Begin work on the implementation and submit a PR
- Iterate based on feedback
Would the maintainers be open to including DDSketch? Are there specific design or compatibility considerations I should address before proceeding?
- Dominant language
- C++
- Stars
- 273
- Forks
- 88
- Avg merge
- 1d 19h
- Merged PRs (30d)
- 9
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from apache/datasketches-cpp
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
apache/datasketches-cpp#499 ·
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
apache/datasketches-cpp#502 · 11 comments · 1 reaction ·
-
Difficulty 3/5 1-2 days Newbie friendliness 45/100
apache/datasketches-cpp#460 · 6 comments ·
-
Difficulty 5/5 Over a week Newbie friendliness 20/100
apache/datasketches-cpp#419 · 6 comments ·
-
Difficulty 5/5 Over a week Newbie friendliness 25/100
apache/datasketches-cpp#416 · 13 comments ·
All issues in apache/datasketches-cpp
Similar issues
-
ai_reviewed
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
ydb-platform/ydb#53869 · 3 comments ·
-
bug cert blocker needs triage
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
project-chip/connectedhomeip#74373 ·
-
upstream update
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
conan-io/conan-center-index#31035 ·
-
Bug
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
documentation
Difficulty 1/5 Under an hour Newbie friendliness 85/100
vllm-project/vllm-ascend#17329 ·