Academic Positions

  • Present 11/2015

    Ph.D. Student

    Computer Science Department, Pisa

Education & Training

  • Mastera.y. 2013/2014

    Master Degree in Computer Science & Networking

    University of Pisa, Scuola Superiore Sant’Anna di studi universitari e perfezionamento, Italy

  • Bachelora.y. 2011/2012

    Bachelor Degree in Computer Engineering

    University of Florence, Italy

  • High Schoola.y. 2008/2009

    Diploma di Maturità Scientifica

    Liceo Scientifico Statale Guido Castelnuovo, Florence, Italy

Honors, Awards and Grants

Clustered Elias-Fano Indexes

Giulio Ermanno Pibiri, Rossano Venturini
ACM Transactions on Information Systems (TOIS), 2017 Journal Paper
@article{TOIS17,
    author      = {Giulio Ermanno Pibiri and Rossano Venturini},
    title       = {Clustered Elias-Fano Indexes},
    journal     = {{ACM} {T}ransactions on {I}nformation {S}ystems ({TOIS})},
    year        = {2017},
    issn        = {1046-8188},
    acmid       = {2987380},
    publisher   = {ACM},
    address     = {New York, NY, USA}
}

Abstract

State-of-the-art encoders for inverted indexes compress each posting list individually. Encoding clusters of posting lists offers the possibility of reducing the redundancy of the lists while maintaining a noticeable query processing speed.
In this paper we propose a new index representation based on clustering the collection of posting lists and, for each created cluster, building an ad-hoc reference list with respect to which all lists in the cluster are encoded with Elias-Fano. We describe a posting lists clustering algorithm tailored for our encoder and two methods for building the reference list for a cluster. Both approaches are heuristic and differ in the way postings are added to the reference list: or according to their frequency in the cluster or according to the number of bits necessary for their representation.
The extensive experimental analysis indicates that significant space reductions are indeed possible, beating the best state-of-the-art encoders.

Dynamic Elias-Fano Representation

Giulio Ermanno Pibiri, Rossano Venturini
Combinatorial Pattern Matching (CPM), 2017 Conference Paper
@inproceedings{CPM17,
    author      = {Giulio Ermanno Pibiri and Rossano Venturini},
    title       = {Dynamic Elias-Fano Representation},
    booktitle   = {{C}ombinatorial {P}attern {M}atching ({CPM})},
    year        = {2017}
}

Abstract

The efficient maintenance of dynamic integer sets is among the most studied problems in Computer Science since its origins. While many solutions for this problem are known to require an optimal amount of time per operation when using polynomial space, whether time optimality can be preserved in the compressed space regime is still an interesting open problem.
In this paper we show that it is possible to store a dynamic ordered set $\mathcal{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 $w = \log u = \Omega(\log n)$ 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 $\mathcal{O}(\min\{1+\log\frac{u}{n}, \log\log n\})$; 2. make $\mathcal{S}$ grow in an append-only fashion by spending $\mathcal{O}(1)$ per inserted element; 3. describe a dynamic data structure supporting random access in $\mathcal{O}(\log n / \log w)$ worst-case, insertions and deletions in $\mathcal{O}(\log n / \log w)$ amortized and predecessor/successor queries in $\mathcal{O}(\min\{1+\log\frac{u}{n}, \log\log n\})$ worst-case time. These time bounds are optimal.