apache / apache/datasketches-cpp
Proposal: Add DDSketch (Relative-Error Quantile Sketch)
- Ngôn ngữ chính
- C++
- Star
- 273
- Fork
- 88
- Merge trung bình
- 2 ngày 2 giờ
- Pull request đã merge (30 ngày)
- 8
Mô tả
## 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?
Hướng dẫn đóng góp
Hướng nghiên cứu
Bắt đầu bằng việc đọc bài báo về DDSketch và tài liệu tham chiếu sketches-java của Datadog. Phần triển khai được đề xuất thuộc về ddsketch.hpp và cần bao gồm tuần tự hóa, giải tuần tự, các bài kiểm thử đơn vị và benchmark. Công việc được coi là hoàn tất khi có một DDSketch độc lập, có thể hợp nhất, với độ chính xác tương đối có thể cấu hình và bộ nhớ bị giới hạn, mà không thay đổi các API hiện có.
Do mô hình lập chỉ mục viết ra từ nội dung của issue.
Đánh giá
- Công nghệ
- cpp
- Lĩnh vực
- data
- Loại issue
- Tính năng
- Độ khó
- 5/5
- Thời gian dự kiến
- Hơn một tuần
- Mức độ hoạt động
- Ít trao đổi
- Độ rõ ràng
- Khá rõ ràng
- Mức phù hợp với người mới
- 45/100