Heapsort in a parallel processing framework

US11775543B1 · kind B1 · utility

Assignee

• SAP SE · DE

Inventors

• Alexander Gellner · Karlsruhe, DE
• Paul Willems · Heidelberg, DE

Key dates

• Filing date: Apr 19, 2022
• Grant date: Oct 3, 2023
• Expiry date: Apr 19, 2042

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/23
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

A method for performing a parallelized heapsort operation may include updating, by a first worker thread, a first buffer while a second worker thread updates a second buffer in parallel. The first worker thread may update the first buffer by adding, to the first buffer, elements from a first partition of a dataset. The second worker thread may update the second buffer by adding, to the second buffer, elements from a second partition of the dataset. Upon the first buffer reaching a threshold size, the first worker thread may acquire a lock for the first worker thread to update a heap based on the first buffer while the second worker thread is prevented from updating the heap based on the second buffer. A result of a top k query comprising a k quantity of smallest elements from the dataset may be generated based on the heap.