The case for a learned sorting algorithm
blog.acolyer.org
The case for a learned sorting algorithm
1–10 of 23 posts
Re: The case for a learned sorting algorithm
#2Is the paper "NN-sort: Neural Network based Data Distribution-aware Sorting" [1] not a year prior to the cited paper? It seems to discuss the same approach.
[1] NN-sort: Neural Network based Data Distribution-aware Sorting: https://arxiv.org/pdf/1907.08817.pdf
Re: The case for a learned sorting algorithm
#3Is the paper "NN-sort: Neural Network based Data Distribution-aware Sorting" [1] not a year prior to the cited paper? It seems to discuss the same approach. [1] NN-sort: Neural Network based Data Distribution-aware Sorting: https://arxiv.org/pdf/1907.08817.pdf
That paper has not been published. You can't claim a paper is prior, just because a draft was available earlier. Incidently it was send to the same conference as the OP paper. But it seems like it wasn't accepted, while the OP paper was.
Re: The case for a learned sorting algorithm
#4Is the paper "NN-sort: Neural Network based Data Distribution-aware Sorting" [1] not a year prior to the cited paper? It seems to discuss the same approach. [1] NN-sort: Neural Network based Data Distribution-aware Sorting: https://arxiv.org/pdf/1907.08817.pdf
That paper has not been published. You can't claim a paper is prior, just because a draft was available earlier. Incidently it was send to the same conference as the OP paper. But it seems like it wasn't accepted, while the OP paper was.
this is not really the norm in computer science. it’s generally expected to cite things on arXiv although it is more of a grey area.
Re: The case for a learned sorting algorithm
#5Earlier quoted context omitted.
That paper has not been published. You can't claim a paper is prior, just because a draft was available earlier. Incidently it was send to the same conference as the OP paper. But it seems like it wasn't accepted, while the OP paper was.
this is not really the norm in computer science. it’s generally expected to cite things on arXiv although it is more of a grey area.
Well they did right by not citing it, as it was rejected for publication.
Re: The case for a learned sorting algorithm
#6>The results show that our approach yields an average 3.38x performance improvement over C++ STL sort, which is an optimized Quick- sort hybrid, 1.49x improvement over sequential Radix Sort, and 5.54x improvement over a C++ implementation of Tim- sort, which is the default sorting function for Java and Python.
This is a lot
Re: The case for a learned sorting algorithm
#7Is the paper "NN-sort: Neural Network based Data Distribution-aware Sorting" [1] not a year prior to the cited paper? It seems to discuss the same approach. [1] NN-sort: Neural Network based Data Distribution-aware Sorting: https://arxiv.org/pdf/1907.08817.pdf
The paper in this post doesn't use neural networks at all. It also includes the time to train the model in the sorting time, which the paper you linked doesn't. NN-sort trains on historic data to sort future data, which requires the distribution to be roughly the same, whearas this algorithm learns online.
Re: The case for a learned sorting algorithm
#8Is the paper "NN-sort: Neural Network based Data Distribution-aware Sorting" [1] not a year prior to the cited paper? It seems to discuss the same approach. [1] NN-sort: Neural Network based Data Distribution-aware Sorting: https://arxiv.org/pdf/1907.08817.pdf
This one doesn’t use neural nets.
Re: The case for a learned sorting algorithm
#9tl,dr: linear spline fitting to approximate a CDF and then recursive bucket sort similar to radix.
Re: The case for a learned sorting algorithm
#10Earlier quoted context omitted.
this is not really the norm in computer science. it’s generally expected to cite things on arXiv although it is more of a grey area.
Well they did right by not citing it, as it was rejected for publication.
that’s not how things work. lots of well-regarded papers are initially rejected in peer review but are commonly discussed and cited while in the submission process at other venues.