Count Min Sketch for Cudax

[ryanjspears]

Hello @PointKernel @sleeepyjack , what are your thoughts on me implementing a Count-Min Sketch for cuco in cudax? cudax cuco has HyperLogLog for distinct counts and fixed_capacity_map for exact counts, but nothing for approximate per-key frequency. A Count-Min Sketch would fill that gap. If you're open to it, I'd model it on hyperloglog and open a PR.

[PointKernel]

@ryanjspears Thanks for proposing this! Do you have a particular workload in mind where exact counting becomes too expensive? It would be helpful to first explore a prototype using existing hashing and histogram utilities, then see what a dedicated sketch API would add in performance or usability.

[sleeepyjack]

Hi @ryanjspears,
Good news! We are working with the Apache Datasketches team to port some of their very well-designed sketches to the GPU and count min sketch is one of them. The project is still in early stages: https://github.com/apache/datasketches-cuda so far we ported HLL and are working on Theta sketches at the moment.

From a scope perspective, I think the implementation should live in datasketches-cuda rather than cuco or cccl but I'm open to a discussion.