apache / apache/datasketches-cpp
Proposal: Add DDSketch (Relative-Error Quantile Sketch)
- Lenguaje dominante
- C++
- Estrellas
- 273
- Forks
- 88
- Merge medio
- 2 d 2 h
- PR fusionados (30 d)
- 8
Descripción
## 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?
Guía de contribución
Línea de trabajo
Empieza leyendo el paper de DDSketch y la referencia sketches-java de Datadog. La implementación propuesta debe estar en ddsketch.hpp e incluir serialización, deserialización, pruebas unitarias y benchmarks. Se considera terminado cuando exista un DDSketch autocontenido y fusionable, con precisión relativa configurable y memoria acotada, sin cambiar las APIs existentes.
Escrito por el modelo de indexación a partir del texto del issue.
Evaluación
- Stack tecnológico
- cpp
- Área
- data
- Tipo de issue
- Nueva funcionalidad
- Dificultad
- 5/5
- Tiempo estimado
- Más de una semana
- Estado de actividad
- Tranquilo
- Claridad
- Bastante claro
- Aptitud para principiantes
- 45/100