apache / apache/datasketches-cpp

Proposal: Add DDSketch (Relative-Error Quantile Sketch)

Open
#457 8 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
273
Forks
88
Avg merge
2d 2h
Merged PRs (30d)
8

Description

## 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.

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?

Contributor guide

Open the contributing guide

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.

Assessment

Tech stack
cpp
Domain
data
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.