An O(N) Sorting Algorithm: Machine Learning Sorting
1–10 of 15 posts
Re: An O(N) Sorting Algorithm: Machine Learning Sorting
#2I've only briefly skimmed the paper, but here's something I've come up with, based on what I read, that might or might not be the same as what they've said, but I think "has legs":
* Randomly choose some fixed sized subset of the data and sort it;
* Based on that, deduce the distribution of the data;
* Based on that, create a destination array, and copy things from the input to roughly the expected right place in the output;
* Run around and fix things.
When sorting numbers, that feels like it has a chance of running quite quickly. For other objects with some other comparison function, not sure how it would work.
Re: An O(N) Sorting Algorithm: Machine Learning Sorting
#3I've only briefly skimmed the paper, but here's something I've come up with, based on what I read, that might or might not be the same as what they've said, but I think "has legs": * Randomly choose some fixed sized subset of the data and sort it; * Based on that, deduce the distribution of the data; * Based on that, create a destination array, and copy things from the input to roughly the expected right place in the…
It works for datasets whose distribution an underlying machine learning model can successfully derive. Otherwise it would fail:
"it works well for big data sets. Because the big data sets usually have fair statistical properties, and its distribution is usually easy to derive and also has some kind of continuity"
Re: An O(N) Sorting Algorithm: Machine Learning Sorting
#4It would have been much more interesting to report on tests of the algorithm on real data.
Re: An O(N) Sorting Algorithm: Machine Learning Sorting
#5I've only briefly skimmed the paper, but here's something I've come up with, based on what I read, that might or might not be the same as what they've said, but I think "has legs": * Randomly choose some fixed sized subset of the data and sort it; * Based on that, deduce the distribution of the data; * Based on that, create a destination array, and copy things from the input to roughly the expected right place in the…
What's the asymptotical complexity of running around and fixing things?
Re: An O(N) Sorting Algorithm: Machine Learning Sorting
#6This seems like a fairly natural generalization of the idea in "The Case for Learned Index Structures" [1]: speed up some classical algorithm based on heuristics by modeling the data with a neural network that can be tuned to the specific task that the general algorithm is applied to.
That said, the O(N) claim is purely sensational. It all depends on being able to determine the distribution parameters with sufficient accuracy in O(N) time, which isn't really guaranteed for all kinds of data you might want to sort.
Re: An O(N) Sorting Algorithm: Machine Learning Sorting
#7Looks interesting after a quick skim, and for simpler datasets "machine learning" shouldn't be needed just some more traditional statistical analysis. I'll have to find time to read it fully and play with the idea.
It'll be interesting to see how the method fairs with messy real-world data over many examples [O(n) is obviously the best case, which is also the best case of the infamous bubble sort if early exit is implemented, how commonly it achieves that performance or close to it is key]. It seems to be a two stage process: the first being to more-or-less sort the input using a simple model of the expected distribution, the second being a tidying exercise that is essentially a more traditional sort.
Re: An O(N) Sorting Algorithm: Machine Learning Sorting
#8Clickbaity paper title. That raised my hackles a bit.
This is basically bucket sort with machine learning thrown in. It is not O(N). O(N) has a very specific mathematical meaning, do not abuse it. It means there exists some fixed K that for every N and every input of size N, the running time is From the conclusion: "For some distributions with less smoothness, it might be difficult to learn the distribution, and if the training fails...the algorithm might fail."
Grr.
Re: An O(N) Sorting Algorithm: Machine Learning Sorting
#9I've only briefly skimmed the paper, but here's something I've come up with, based on what I read, that might or might not be the same as what they've said, but I think "has legs": * Randomly choose some fixed sized subset of the data and sort it; * Based on that, deduce the distribution of the data; * Based on that, create a destination array, and copy things from the input to roughly the expected right place in the…
What's the asymptotical complexity of running around and fixing things?
That stage is presumably a more traditional sort operation. If the first stage does a good job of estimating the correct order this could also be O(n) or as close to as makes no odds. If the set isn't modelled properly by the earlier stages it will still be O(n log n). Obviously that operation needs to be an algorithm that can take advantage of partially pre-sorted input.
Re: An O(N) Sorting Algorithm: Machine Learning Sorting
#10Clickbaity paper title. That raised my hackles a bit. This is basically bucket sort with machine learning thrown in. It is not O(N). O(N) has a very specific mathematical meaning, do not abuse it. It means there exists some fixed K that for every N and every input of size N, the running time is From the conclusion: "For some distributions with less smoothness, it might be difficult to learn the distribution, and if t…
Also, they end up with a O(N*M) algorithm. They claim M is small, but it needs to be strictly smaller than logN if they want to be better than O(NlogN). A terabyte is 10^12. Thus log(N) is 12. They have 100 hidden neurons which is their M. So their algorithm isn't asymptotically faster, unless they go in N>10^100 with that amount of hidden neurons.