apache
DDSketch
Description
This PR implements DDSketch and closes #457. The design follows the core ideas of the original DDSketch paper and the implementations in other libraries. I have aimed to keep the API consistent with the existing sketches, especially the other quantile sketches. There might still be some work to do (e.g., adding additional methods or refinements), but I’d like to hear your opinions on the design and implementation so far before proceeding further.
Implementation
This implementation currently requires C++20, primarily for the use of concepts and constrained templates. DDSketch is templated over a Store concept, rather than relying on a common base class and virtual methods.
If C++20 adoption is not desired, I can rework the code to remain compatible with C++11 by limiting the implementation to collapsing dense stores and removing concept-based templates. I’d appreciate the maintainers’ input on which direction to take before finalizing.
Thank you for the detailed feedback @leerho .
I understand the requirements for adding a new sketch to the repository, and I am happy to make the requested adjustments.
For C++ version compatibility, I can update the implementation so that it is fully compliant with C++11.
On the documentation and evaluation side, I have already implemented Python bindings (I haven't opened the PR in datasketches-python yet) and used them to run an initial comparison between DDSketch and T-Digest in a jupyter notebook. I am currently working on a more thorough characterization similar to the analysis in issue #416, including both performance and memory usage comparisons.
I am also preparing a detailed description of the sketch that can be added to the website. This will cover the behavior of the sketch, its performance characteristics, and how it compares with the other quantile sketches in the library.
Please let me know if there is anything else you would like me to include or adjust.