Given an integer array A, the prefix-sum problem is to answer sum(i) queries that return the sum of the elements in A[0.i], knowing that the integers in A can 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 G. E.;
2021-01-01
Abstract
Given an integer array A, the prefix-sum problem is to answer sum(i) queries that return the sum of the elements in A[0.i], knowing that the integers in A can 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 | |
|---|---|---|---|
|
SPE2021.pdf
accesso aperto
Tipologia:
Documento in Post-print
Licenza:
Accesso libero (no vincoli)
Dimensione
1.08 MB
Formato
Adobe PDF
|
1.08 MB | Adobe PDF | Visualizza/Apri |
I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
