Given an integer arrayA, theprefix-sum problemis to answersum(i)queries that return the sum of the elements inA[0..i], knowing that the integers inAcan be changed. It is a classic problem in data structure design with a wide range of applications in computing from coding to databases. In this work, we propose and compare practical solutions to this problem, showing that new trade-offs between the performance of queries and updates can be achieved on modern hardware.
Practical trade-offs for the prefix-sum problem
Pibiri GE;
2020
Abstract
Given an integer arrayA, theprefix-sum problemis to answersum(i)queries that return the sum of the elements inA[0..i], knowing that the integers inAcan be changed. It is a classic problem in data structure design with a wide range of applications in computing from coding to databases. In this work, we propose and compare practical solutions to this problem, showing that new trade-offs between the performance of queries and updates can be achieved on modern hardware.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_435491-doc_156910.pdf
Open Access dal 22/10/2021
Descrizione: Practical trade-offs for the prefix-sum problem
Tipologia:
Versione Editoriale (PDF)
Dimensione
3.62 MB
Formato
Adobe PDF
|
3.62 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
