We show that it is possible to store a dynamic ordered set S(n,u) of n integers drawn from a bounded universe of size u in space close to the information-theoretic lower bound and yet preserve the asymptotic time optimality of the operations. Our results leverage on the Elias-Fano representation of S(n, u) which takes EF(S(n, u)) = n⌊log u/n⌋ + 2n bits of space and can be shown to be less than half a bit per element away from the information-theoretic minimum. Considering a RAM model with memory words of θ(log u) bits, we focus on the case in which the integers of S are drawn from a polynomial universe of size u = nγ, for any γ= θ(1). We represent S(n,u) with EF(S(n, u)) + o(n) bits of space and: 1. support static predecessor/successor queries in O(min{1 + log u/n, log log n}); 2. make S grow in an append-only fashion by spending O(1) per inserted element; 3. support random access in O(log n/log log n) worst-case, insertions/deletions in O(log n/log log n) amortized and predecessor/successor queries in O(min{1 + log u/n, log log n}) worst-case time. These time bounds are optimal.

Dynamic elias-fano representation

Pibiri G. E.;Venturini R.
2017-01-01

Abstract

We show that it is possible to store a dynamic ordered set S(n,u) of n integers drawn from a bounded universe of size u in space close to the information-theoretic lower bound and yet preserve the asymptotic time optimality of the operations. Our results leverage on the Elias-Fano representation of S(n, u) which takes EF(S(n, u)) = n⌊log u/n⌋ + 2n bits of space and can be shown to be less than half a bit per element away from the information-theoretic minimum. Considering a RAM model with memory words of θ(log u) bits, we focus on the case in which the integers of S are drawn from a polynomial universe of size u = nγ, for any γ= θ(1). We represent S(n,u) with EF(S(n, u)) + o(n) bits of space and: 1. support static predecessor/successor queries in O(min{1 + log u/n, log log n}); 2. make S grow in an append-only fashion by spending O(1) per inserted element; 3. support random access in O(log n/log log n) worst-case, insertions/deletions in O(log n/log log n) amortized and predecessor/successor queries in O(min{1 + log u/n, log log n}) worst-case time. These time bounds are optimal.
2017
Leibniz International Proceedings in Informatics, LIPIcs
File in questo prodotto:
File Dimensione Formato  
CPM2017.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Accesso libero (no vincoli)
Dimensione 501.51 kB
Formato Adobe PDF
501.51 kB Adobe PDF Visualizza/Apri

I documenti in ARCA 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: https://hdl.handle.net/10278/5023383
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact