LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization

Autor:	Carvalho, Ivan, Lawrence, Ramon
Rok vydání:	2023
Předmět:	Computer Science - Machine Learning Computer Science - Databases
Druh dokumentu:	Working Paper
DOI:	10.1145/3603719.3603731
Popis:	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. Comment: Published in SSDBM 2023
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2307.08637 Zobrazit plný text záznamu View this record from Arxiv