apache / apache/datasketches-cpp

Proposal: Add DDSketch (Relative-Error Quantile Sketch)

Abierto
#457 8 comentarios 0 reacciones 0 asignados Ver en GitHub
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

Abrir la 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

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.