apache / apache/datasketches-cpp
Proposal: Add DDSketch (Relative-Error Quantile Sketch)
- Langage dominant
- C++
- Étoiles
- 273
- Forks
- 88
- Merge moyen
- 2 j 2 h
- PR mergées (30 j)
- 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?
Guide de contribution
Ouvrir le guide de contribution
Piste de recherche
Commencez par lire l’article sur DDSketch et la référence sketches-java de Datadog. L’implémentation proposée doit se trouver dans ddsketch.hpp et inclure la sérialisation, la désérialisation, des tests unitaires et des benchmarks. Le travail est considéré comme terminé lorsqu’un DDSketch autonome et fusionnable, avec une précision relative configurable et une mémoire bornée, est disponible, sans modifier les APIs existantes.
Rédigé par le modèle d'indexation à partir du texte de l'issue.
Évaluation
- Stack technique
- cpp
- Domaine
- data
- Type d'issue
- Fonctionnalité
- Difficulté
- 5/5
- Temps estimé
- Plus d'une semaine
- Activité
- Calme
- Clarté
- Plutôt claire
- Accessibilité débutants
- 45/100