mlsanityData to 14 Oct 2026

LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization

arXiv 2307.08637 ↗First posted 17 Jul 2023cs.LG cs.DBcited by 0

Not on the map. Why?

Abstract (arXiv)

This work analyzes and parallelizes LearnedSort, the novel algorithm that sorts using machine learning models based on the cumulative distribution function. LearnedSort is analyzed under the lens of algorithms with predictions, and it is argued that LearnedSort is a learning-augmented SampleSort. A parallel LearnedSort algorithm is developed combining LearnedSort with the state-of-the-art SampleSort implementation, IPS4o. Benchmarks on synthetic and real-world datasets demonstrate improved parallel performance for parallel LearnedSort compared to IPS4o and other sorting algorithms.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 21 of its 34 references that are in the map. First posted on arXiv 17 Jul 2023.

Builds on

21 of 34 references.

References · 21

  1. 2018Competitive caching with machine learned advicecited by 195
  2. 2017The Case for Learned Index Structurescited by 188
  3. 2020Algorithms with Predictionscited by 153
  4. 2020RadixSpline: A Single-Pass Learned Indexcited by 31
  5. 2020Benchmarking Learned Indexescited by 27
  6. 2019The PGM-index: a multicriteria, compressed and learned approach to data indexingcited by 17
  7. 2020The Case for Learned Spatial Indexescited by 9
  8. 2021A Critical Analysis of Recursive Model Indexescited by 9
  9. 2021Bounding the Last Mile: Efficient Learned String Indexingcited by 6
  10. 2021Towards Practical Learned Indexingcited by 3
  11. 2019LISA: Towards Learned DNA Sequence Searchcited by 2
  12. 2022Vectorized and performance-portable Quicksortcited by 2
9 more
  1. 2013Parallel String Sample Sortcited by 1
  2. 2016BlockQuicksort: How Branch Mispredictions don't affect Quicksortcited by 1
  3. 2016Quicksort with median of medians is considered practicalcited by 1
  4. 2018Histogram Sort with Samplingcited by 1
  5. 2019Engineering Faster Sorters for Small Sets of Itemscited by 1
  6. 2020Engineering In-place (Shared-memory) Sorting Algorithmscited by 1
  7. 2021Pattern-defeating Quicksortcited by 1
  8. 2021Defeating duplicates: A re-design of the LearnedSort algorithmcited by 1
  9. 2023Using Learned Indexes to Improve Time Series Indexing Performance on Embedded Sensor Devicescited by 1

Built on by

Not cited yet.