apache / apache/datasketches-cpp

Proposal: Add DDSketch (Relative-Error Quantile Sketch)

Ouverte
#457 8 commentaires 0 réactions 0 personnes assignées Voir sur GitHub
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

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.