apache / apache/datasketches-cpp

Proposal: Add DDSketch (Relative-Error Quantile Sketch)

Aperta
#457 8 commenti 0 reazioni 0 assegnatari Vedi su GitHub
Lingua principale
C++
Stelle
273
Fork
88
Merge medio
2g 2h
PR unite (30g)
8

Descrizione

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

Guida per i contributori

Apri la guida per i contributori

Direzione di ricerca

Inizia leggendo il paper su DDSketch e la reference sketches-java di Datadog. L’implementazione proposta deve trovarsi in ddsketch.hpp e includere serializzazione, deserializzazione, test unitari e benchmark. Il lavoro è considerato completato quando è disponibile un DDSketch autonomo e unibile, con accuratezza relativa configurabile e memoria limitata, senza modificare le API esistenti.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Valutazione

Stack tecnologico
cpp
Ambito
data
Tipo di issue
Funzionalità
Difficoltà
5/5
Tempo stimato
Più di una settimana
Stato di attività
Tranquilla
Chiarezza
Abbastanza chiara
Idoneità per principianti
45/100

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.