LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization

Abstract

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.

arXiv commentPublished in SSDBM 2023

References in corpus (6)

• The PGM-index: a multicriteria, compressed and learned approach to data indexing
• Pattern-defeating Quicksort
• BlockQuicksort: How Branch Mispredictions don't affect Quicksort
• Quicksort with median of medians is considered practical
• Using Learned Indexes to Improve Time Series Indexing Performance on Embedded Sensor Devices
• A Critical Analysis of Recursive Model Indexes