2026-07-22T01:42:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7324 2024-03-06T10:40:09Z ddc:004 open_access

Dynamic Elias-Fano Representation Pibiri, Giulio Ermanno Venturini, Rossano succinct data structures integer sets predecessor problem Elias-Fano We show that it is possible to store a dynamic ordered set S of n integers drawn from a bounded universe of size u in space close to the information-theoretic lower bound and preserve, at the same time, the asymptotic time optimality of the operations. Our results leverage on the Elias-Fano representation of monotone integer sequences, which can be shown to be less than half a bit per element away from the information-theoretic minimum. In particular, considering a RAM model with memory word size Theta(log u) bits, when integers are drawn from a polynomial universe of size u = n^gamma for any gamma = Theta(1), we add o(n) bits to the static Elias-Fano representation in order to: 1. support static predecessor/successor queries in O(min{1+log(u/n), loglog n}); 2. make S grow in an append-only fashion by spending O(1) per inserted element; 3. describe a dynamic data structure supporting random access in O(log n / loglog n) worst-case, insertions/deletions in O(log n / loglog n) amortized and predecessor/successor queries in O(min{1+log(u/n), loglog n}) worst-case time. These time bounds are optimal. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giulio Ermanno Pibiri and Rossano Venturini 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.30 urn:nbn:de:0030-drops-73244 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.30 eng https://creativecommons.org/licenses/by/3.0/legalcode