We consider the well-studied partial sums problem in succint space where one is to maintain an array of n k-bit integers subject to updates such that partial sums queries can be efficiently answered. We present two succint versions of the Fenwick Tree – which is known for its simplicity and practicality. Our results hold in the encoding model where one is allowed to reuse the space from the input data. Our main result is the first that only requires nk + o(n) bits of space while still supporting sum/update in O(logbn)/O(blogbn) time where 2 ≤ b ≤ log O(1)n. The second result shows how optimal time for sum/update can be achieved while only slightly increasing the space usage to nk + o(nk) bits. Beyond Fenwick Trees, the results are primarily based on bit-packing and sampling – making them very practical – and they also allow for simple optimal parallelization.

Succinct partial sums and fenwick trees / Bille, P.; Christiansen, A. R.; Prezza, N.; Skjoldjensen, F. R.. - (2017), pp. 91-96. ((Intervento presentato al convegno 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017 tenutosi a Palermo nel 26-29 settembre 2017 [10.1007/978-3-319-67428-5_8].

Succinct partial sums and fenwick trees

Prezza N.;
2017

Abstract

We consider the well-studied partial sums problem in succint space where one is to maintain an array of n k-bit integers subject to updates such that partial sums queries can be efficiently answered. We present two succint versions of the Fenwick Tree – which is known for its simplicity and practicality. Our results hold in the encoding model where one is allowed to reuse the space from the input data. Our main result is the first that only requires nk + o(n) bits of space while still supporting sum/update in O(logbn)/O(blogbn) time where 2 ≤ b ≤ log O(1)n. The second result shows how optimal time for sum/update can be achieved while only slightly increasing the space usage to nk + o(nk) bits. Beyond Fenwick Trees, the results are primarily based on bit-packing and sampling – making them very practical – and they also allow for simple optimal parallelization.
978-3-319-67427-8
978-3-319-67428-5
Fenwick tree; Parallel; Partial sums; Succinct
Succinct partial sums and fenwick trees / Bille, P.; Christiansen, A. R.; Prezza, N.; Skjoldjensen, F. R.. - (2017), pp. 91-96. ((Intervento presentato al convegno 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017 tenutosi a Palermo nel 26-29 settembre 2017 [10.1007/978-3-319-67428-5_8].
File in questo prodotto:
File Dimensione Formato  
fenwick.pdf

Solo gestori archivio

Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 318.75 kB
Formato Adobe PDF
318.75 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/194131
Citazioni
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact