5 ms·
It is interesting to see that this topic which is around the academic world since 2004 is gaining popularity only now. An interesting thing is that you can fin
by fabiofumarola 9y ago
It is interesting to see that this topic which is around the academic world since 2004 is gaining popularity only now.
An interesting thing is that you can find some of these concepts implemented in apache spark (count approx) and into BlinkDB.
While, from a theoretical point of view many result are relate d to statistical bound like Chernoff bound and Chebyshev inequality.
During my phd I found this topic interesting and promising to answer to mine data with a verified error bound for precision/recall and elapsed time.
To go deeply into this topic I suggest the book Knowledge Discovery from
Data Streams http://www.liaad.up.pt/area/jgama/DataStreamsCRC.pdf http://www.liaad.up.pt/area/jgama/DataStreamsCRC.pdf and other books written by Joao Gama.
- lorenzhs 9y agoAgreed, streaming algorithms and sketches are a fascinating topic. The article's author, Graham Cormode, has been conducting research in that area for a long time and is one of the co-authors of the Count-Min Sketch paper. Basically a Count-Min Sketch is the same thing as an undersized counting Bloom filter, but it's used quite differently. This allows for loads of interesting operations. First, there's the estimated number of occurrences of an element (how often has it been added?), but it can do more complex things as well, such as quantiles and heavy hitters.