apache / apache/datasketches-cpp
Proposal: Add DDSketch (Relative-Error Quantile Sketch)
- 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