Open Collections

UBC Undergraduate Research

Towards Parallel Learned Sorting Carvalho, Ivan

Abstract

We introduce a new sorting algorithm that is the combination of ML-enhanced sorting with the In-place Super Scalar Sample Sort (IPS4o). The main contribution of our work is to achieve parallel ML-enhanced sorting, as previous algorithms were limited to sequential implementations. We introduce the In-Place Parallel Learned Sort (IPLS) algorithm and compare it extensively against other sorting approaches. IPLS combines the IPS4o framework with linear models trained using the Fastest Minimum Conflict Degree algorithm to partition data. The experimental results do not crown IPLS as the fastest algorithm. However, they do show that IPLS is competitive among its peers and that using the IPS4o framework is a promising approach towards parallel learned sorting.

Item Metadata

Title
Towards Parallel Learned Sorting
Creator
Carvalho, Ivan
Date Issued
2022-04
Description
We introduce a new sorting algorithm that is the combination of ML-enhanced sorting with the In-place Super Scalar Sample Sort (IPS4o). The main contribution of our work is to achieve parallel ML-enhanced sorting, as previous algorithms were limited to sequential implementations. We introduce the In-Place Parallel Learned Sort (IPLS) algorithm and compare it extensively against other sorting approaches. IPLS combines the IPS4o framework with linear models trained using the Fastest Minimum Conflict Degree algorithm to partition data. The experimental results do not crown IPLS as the fastest algorithm. However, they do show that IPLS is competitive among its peers and that using the IPS4o framework is a promising approach towards parallel learned sorting.
Genre
Graduating Project
Type
Text
Language
eng
Series
University of British Columbia. COSC 449
Date Available
2022-08-24
Provider
Vancouver : University of British Columbia Library
Rights
Attribution 4.0 International
DOI
10.14288/1.0417515
URI
http://hdl.handle.net/2429/82507
Affiliation
Science, Irving K. Barber Faculty of (Okanagan); Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
Peer Review Status
Unreviewed
Scholarly Level
Undergraduate
Rights URI
http://creativecommons.org/licenses/by/4.0/
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

Rights

Attribution 4.0 International