Re:Best-Ever Algorithm Found for Huge Streams of Data
by mcroydon on Monday October 30, 2017 @03:57AM
(#15583608)
The original paper (https://arxiv.org/abs/1604.01357) from 2016 goes in to more detail.
Re:Best-Ever Algorithm Found for Huge Streams of Data
by AstralStorm on Monday October 30, 2017 @05:00AM
(#15583763)
Thank you for the link. Interesting, they used the graph resampling and r-tree approaches already in use for certain kinds of machine learning. (Esp. approximate eigenvalue based classifiers)
Very well written too. Unfortunately the approach described only works for dense countable data that is linearly separable (eta spectral clusters, in fact even stronger assumption) - which still makes it quite useful as a database index.
Re:Best-Ever Algorithm Found for Huge Streams of Data
by wjnc on Monday October 30, 2017 @05:50AM
(#15583916)
If you know what's going on, the title might be clickbait. But I looked at the abstract (via the link in the article on Quanta Magazine) and understood none. Read the article and understood some. They explained the Big-O, the algorithm and the underlying graph that's being created. For me the bravour in the title is (just) fitting.
Re:Best-Ever Algorithm Found for Huge Streams of Data
by AstralStorm on Monday October 30, 2017 @03:54AM
(#15583601)
So this is essentially short complete Markov chain with recovery? What is the secret to performance in this probabilistic compressor? Word size alignment and locality?
Is this based on new extended variant of Ross's theorem? (multivariate case)
TL;DR: split your items by chunck of 8 bits. Store for each chunck A the number of time you saw it before the chunck B followed by C. Then you keep track of only 2^24 counters instead of one counter by possible item. Then using some graph algorithm (the interesting part, which is not explained in the article) you can use those weighted edges to reconstruct the most frequent items with a high confidence.