t-digest VS RoaringBitmap

I am enamored by data structures in the sketch/summary/probabilistic family: t-digest[1], q-digest[2], count-min sketch[3], matrix-sketch[4], graph-sketch[5][6], Misra-Gries sketch[7], top-k/spacesaving sketch[8], &c.

What I like about them is that they give me a set of engineering tradeoffs that I typically don't have access to: accuracy-speed[9] or accuracy-space. There have been too many times that I've had to say, "I wish I could do this, but it would take too much time/space to compute." Most of these problems still work even if the accuracy is not 100%. And furthermore, many (if not all of these) can tune accuracy to by parameter adjustment anyways. They tend to have favorable combinatorial properties ie: they form monoids or semigroups under merge operations. In short, a property of data structures that gave me the ability to solve problems I couldn't before.

I hope they are as useful or intriguing to you as they are to me.

1. https://github.com/tdunning/t-digest

2. https://pdsa.readthedocs.io/en/latest/rank/qdigest.html

3. https://florian.github.io/count-min-sketch/

4. https://www.cs.yale.edu/homes/el327/papers/simpleMatrixSketc...

5. https://www.juanlopes.net/poly18/poly18-juan-lopes.pdf

6. https://courses.engr.illinois.edu/cs498abd/fa2020/slides/20-...

7. https://people.csail.mit.edu/rrw/6.045-2017/encalgs-mg.pdf

8. https://www.sciencedirect.com/science/article/abs/pii/S00200...

9. It may better be described as error-speed and error-space, but I've avoided the term error because the term for programming audiences typically evokes the idea of logic errors and what I mean is statistical error.

On sketches, there is a genre of structure for estimating histogram-like statistics (median, 99th centile, etc) in fixed space, which i really like. Two examples:

t-digest https://github.com/tdunning/t-digest

DDSketch https://github.com/DataDog/sketches-java

Ah, I misunderstood what you meant. If you are reporting static buckets I get how that is better than what folks typically do but how do you know the buckets a priori? Others back their histograms with things like https://github.com/tdunning/t-digest. It is pretty powerful as the buckets are dynamic based on the data and histograms can be added together.

There are some newer data structures that take this to the next level such as T-Digest[1], which remains extremely accurate even when determining percentiles at the very tail end (like 99.999%)

[1]: https://arxiv.org/pdf/1902.04023.pdf / https://github.com/tdunning/t-digest

This is pretty cool. The title would be a bit more descriptive if it were “Fast Rolling Quantile Filters for Python”, since the high-pass/low-pass filter functionality seems to be the focus.

The README mentions it uses binary heaps - if you’re willing to accept some (bounded) approximation, then it should be possible to reduce memory usage and somewhat reduce runtime by using a sketching data structure like Dunning’s t-digest: https://github.com/tdunning/t-digest/blob/main/docs/t-digest....

There is an open source Python implementation, although I haven’t used it and can’t vouch for its quality: https://github.com/CamDavidsonPilon/tdigest

However, I would love compressed (not just packed) bitsets too, which is something different to me. I would make it another class with a similar interface, based on something like roaring. It doesn't need to be in the standard, but it would be nice if the API was a such that one could easily swap implementations.

As an aside if you find yourself having to compute them on the fly, know that the Roaring Bitmaps libraries is the way to go [1]. The bitmaps are compressed, and can be streamed directly into SIMD computations (batching XORs and popcnts 256 bits wide!). The Jaccard index is just intersection_len / union_len [2] away

[1] https://roaringbitmap.org/

[2] https://roaringbitmap.readthedocs.io/en/latest/#roaringbitma...

Use a two stage approach, with a bloom/cuckoo filter stored as a https://roaringbitmap.org/ in memory. Then a secondary key/value store on disk (bolt or anything else).

If you are solely supporting intersection (i.e. you consider all phrase searches to be boolean OR operations on all terms) then roaring bitmaps is probably not a perfect solution to any of your problems.

There are some algorithms that have been optimized for intersect, union, remove (OR, AND, NOT) that work extremely well for sorted lists but the problem is usually: how to efficiently sort the lists that you wish to perform boolean operations on, so that you can then apply the roaring bitmap algorithms on them.

https://roaringbitmap.org/

I wonder if there's a huge difference in efficiency between RoaringBitmap and CQEngine. I used CQEngine a few years back and it turned out really great. Never tried RoaringBitmap, though.

This might be a good fit for roaring bitmaps [1] or Minimal Perfect Hashing

[1] http://roaringbitmap.org/

might be able to use one of the roaring bitmap implementations https://roaringbitmap.org/ via ffi, or port one to CL. been using them from clojure via java implementation, great lib.