apache / apache/datasketches-cpp

Proposal: Add DDSketch (Relative-Error Quantile Sketch)

オープン
#457 コメント 8 件 リアクション 0 件 担当者 0 名 GitHub で見る
主要言語
C++
スター
273
フォーク
88
平均マージ
2日 2時間
マージ済み PR(30日)
8

説明

## 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?

コントリビューションガイド

コントリビューションガイドを開く

調査の方向性

まず DDSketch の論文と Datadog の sketches-java リファレンスを読みます。提案する実装は ddsketch.hpp に配置し、シリアライズ、デシリアライズ、ユニットテスト、ベンチマークを含める必要があります。既存の API を変更せず、相対精度を設定可能でメモリ使用量が制限された、自己完結型でマージ可能な DDSketch ができれば完了です。

索引モデルが issue の本文から書いたものです。

評価

技術スタック
cpp
領域
data
issue の種類
機能追加
難易度
5/5
見積もり時間
1週間以上
活発さ
静か
明瞭さ
おおむね明確
初心者へのやさしさ
45/100

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。