Relazione di adempimento al Dottorato di Ricerca in Informatica
Dipartimento di Informatica Università di Pisa
Giulio Ermanno Pibiri
Durante i tre anni di Dottorato di Ricerca in Informatica, il sottoscritto, Giulio Ermanno Pibiri, ha svolto la propria attività di ricerca nell’ambito degli algoritmi e strutture dati per la gestione di grandi quantità di dati. In particolare, la sua Tesi tratta la progettazione di strutture dati compresse che non sacrificano la velocità di accesso ai dati. Queste due tematiche, compressione dati e accesso rapido, sono state da sempre considerate in conflitto l’una con l’altra. Tuttavia, i risultati di ricerca conseguiti dal candidato dimostrano come esse possano oggigiorno convivere in un’unica soluzione, combinando l’efficienza in spazio a quella in tempo.
Quindi, la tesi, ad alto livello, può essere riassunta nel seguente modo: la progettazione di strutture dati compresse implica l’esecuzione più rapida degli algoritmi.
Segue un breve descrizione dei risultati di ricerca pubblicati durante i tre anni. La relazione termina con la lista dei corsi seguiti assieme agli esami sostenuti, i seminari cui il candidato ha partecipato e indicazione riguardo ai soggiorni all’estero effettuati.
1. Risultati di ricerca
Il primo problema trattato è fondamentale nell’Informatica fin dai suoi albori: il problema del dizionario ordinato e dinamico [Cormen, Leiserson, Rivest, Stein 2009]. Il problema è quello di mantenere una collezione ordinata di oggetti soggetta a operazioni di modifica (aggiunta e cancellazione di un oggetto dal dizionario) e di interrogazione (ricerca di un oggetto nel dizionario). Essendo un problema così fondamentale, molte strutture dati sono state proposte e usate in letteratura. Per collezioni generiche di oggetti che possono essere acceduti tramite confronto, il problema ammette una soluzione ottimale in tempo logaritmico nel numero di elementi presenti nel dizionario, usando una struttura dati appartenente alla famiglia degli alberi di ricerca bilanciati. Tuttavia, quando gli oggetti memorizzati sono interi è possibile fare di meglio. Esistono diverse strutture dati in letteratura che raggiungono tempi asintotici ottimali per tutte le operazioni [Fredman, Willard, 1993; Patrascu, Thorup, 2014]. Relativamente poca attenzione ha invece ricevuto lo spazio occupato da tali strutture, che è lineare nel numero di elementi memorizzati nel dizionario. Ci siamo pertanto chiesti se fosse possibile combinare l’ottimalità in tempo delle strutture proposte in letteratura con l’ottimalità in spazio dell’algoritmo di compressione Elias-Fano. Nel lavoro intitolato Dynamic Elias-Fano Representation [Pibiri, Venturini, CPM 2017], abbiamo risposto positivamente a questa domanda, descrivendo una struttura dati che implementa tutte le operazioni richieste dal problema del dizionario in tempo ottimale e sfrutta l’algoritmo di Elias-Fano per ottenere spazio succinto. L’articolo è stato pubblicato su un simposio di algoritmica teorica: Symposium on Combinatorial Pattern Matching (CPM). Il sottoscritto ha partecipato alla relativa conferenza internazionale, tenutasi a Varsavia (Polonia) 04/07/2017-06/07/2017, durante la quale ha presentato oralmente i contenuti dell’articolo.
Il secondo problema affrontato tratta il problema di rappresentare liste ordinate di interi in modo tale da minimizzarne i requisiti di spazio e tempo di decodifica. Tale problema è uno dei più studiati e fondamentali in Informatica, dato che tali liste ordinate di interi occorrono in cruciali applicazioni pratiche. Fra tutte, citiamo la più importante: i motori di ricerca. Ad alto livello, un motore di ricerca è un sistema capace di individuare quali documenti (intesi come frammenti di testo, e.g., le pagine Web) contengono le parole chiave digitate dall’utente. Dato l’enorme numero di documenti gestiti dal motore, è necessario l’utilizzo di una struttura dati compressa che possa restituire il risultato in
La struttura dati che costituisce il cuore di ogni motore di ricerca moderno è l’indice invertito. Tale struttura dati è proprio una collezione di liste ordinate di interi. Tali liste vengono costruite nel modo seguente: per ogni termine distinto presente nei documenti che il motore deve cercare, vengono memorizzati gli identificativi dei documenti che contengono tale termine. Come già fatto presente, dato il numero di documenti e il numero di termini distinti, le dimensioni di un indice invertito sono gigantesche: centinaia di milioni di liste; ogni lista contenente da poche migliaia fino a miliardi di interi. Dato un insieme di termini corrispondente alle parole che l’utente intende cercare nell’indice, viene eseguita l’intersezione tra le liste invertite associate ai termini. L’intersezione rappresenta l’insieme dei documenti che contengono tutti i termini cercati dall’utente. Risulta quindi essere di fondamentale importanza che tali intersezioni vengano eseguite velocemente e direttamente sulle sequenze compresse.
Siamo pertanto interessati a ridurre lo spazio dell’indice in modo tale che i tempi di accesso alle liste compresse siano paragonabili a quelli dei metodi proposti allo stato dell’arte.
Per tale problema abbiamo studiato, proposto e implementato, tre diverse soluzioni che descriviamo nel seguito.
La prima idea è quella di sfruttare la ridondanza implicita presente negli indici invertiti. Le liste degli indici invertiti, infatti, hanno un elevato grado di ridondanza: molti interi sono condivisi dalle liste di termini tra loro semanticamente correlati. Come ridurre tale ridondanza in modo tale che le interrogazioni risultino al tempo stesso molto veloci è l’arduo problema preso in considerazione. La nostra tecnica prevede tre passi.
1. Raggruppare tra loro liste il più simili possibile.
2. Per ogni gruppo, sintetizzare una lista di riferimento rispetto alla quale tutte le liste del gruppo sono codificate. Codificare una lista rispetto a quella di riferimento significa suddividere la sua rappresentazione in due segmenti: una parte di intersezione ed una parte residua. La parte di intersezione è altamente più comprimibile rispetto alla rappresentazione originale.
3. Comprimere separatamente i due segmenti (intersezione e residuo) usando un algoritmo allo stato dell’arte, che prende il nome di Elias-Fano [Elias 1974, Fano 1971].
Il lavoro che esplora quest’idea [Pibiri, Venturini, TOIS 2017], intitolato Clustered Elias-Fano Indexes, è stato pubblicato sulla rivista più prestigiosa nell’ambito dell’Information Retrieval: ACM Transactions on Information Systems (TOIS). I risultati sperimentali dimostrano un miglioramento sostanzioso dello spazio (fino all’11% di spazio in meno) rispetto alle migliori tecniche allo stato dell’arte [Ottaviano, Venturini 2014; Moffat, Stuiver 2000], rendendo indici invertiti più compatti rispetto a quello che era considerato il migliore algoritmo di compressione fin dagli anni 2000, Binary Interpolative Coding [Moffat, Stuiver 2000] e sensibilmente più veloci.
La seconda idea riguarda uno specifico algoritmo di compressione, chiamato Variable-Byte. Tale algoritmo è noto come essere il più veloce il letteratura nel decodificare le liste compresse. Tuttavia, è inefficiente in spazio, specialmente quando gli interi da comprimere sono piccoli, come è il caso degli indici invertiti. Ci siamo, pertanto, chiesti se fosse possible migliorarne lo spazio compresso di rappresentazione senza sacrificarne l’efficienza di decodifica.
Per rispondere a tale domanda, abbiamo proposto un algoritmo che divide una lista invertita in partizioni di lunghezza variabile per migliorarne lo spazio. I risultati ottenuti dimostrano che è così possibile ridurre lo spazio di Variable-Byte di oltre il 50%. Abbiamo inoltre dimostrato che l’algoritmo proposto è ottimale e la sua complessità è lineare nella lunghezza della lista, rendendolo molto veloce anche su input molto grandi. Con una vasta analisi sperimentale abbiamo, infine, mostrato sperimentalmente che l’efficienza nel decodificare le liste è del tutto mantenuta.
Il lavoro intitolato Variable-Byte Encoding is Now Space Efficient Too [Pibiri, Venturini 2018, ArXiv 1804.10949] è correntemente sotto revisione da uno dei journal più prestigiosi nell’ambito della gestione di grandi quantità di dati, chiamato IEEE Transactions on Knowledge and Data Engineering (IEEE TKDE).
La terza soluzione proposta propone di comprimere le liste invertite mediante l’uso di un dizionario di sottosequenze comuni di interi. Se il dizionario è piccolo, diciamo contenente al massimo 65,536 sottosequenze, è possible descrivere l’intera sottosequenza con 16 bits. Inoltre, se la sottosequenza descritta è lunga 8 interi, allora stiamo usando 16/8=2 bits per intero; se è lunga 16, stiamo usando 1 bit per intero, ecc. Quindi, la tecnica permette di raggiungere ottimi livelli di compressione, paragonabili a quelli dei migliori compressori allo stato dell’arte.
Con una vasta analisi sperimentale, abbiamo anche dimostrato che è possibile ottenere enorme velocità di decompressione, dato che con un singolo accesso al dizionario è possibile decodificare un’intera sottosequenza.
Il lavoro [Pibiri, Petri, Moffat 2018], svolto in collaborazione con Alistair Moffat e Matthias Petri dell’Università di Melbourne, è stato pubblicato e presentato durante la conferenza internazionale WSDM a Melbourne (Australia) durante 11-15/02/2019. Il lavoro è stato svolto mentre il sottoscritto era in visita all’Università di Melbourne, dal 01/05/2018 and 01/10/2018.
Il terzo problema trattato riguarda invece la rappresentazione compatta di dizionari di stringhe, nella fattispecie di corte stringhe che prendono il nome di N-grammi. Tali stringhe sono costituite da al più N parole. Esse vengono estratte mediante una finestra di lunghezza variabile, al più lunga N parole, che scorre sul testo. Per ogni stringa distinta estratta siamo interessati a memorizzare la sua frequenza, i.e., quante volte essa appare nel testo, in una struttura dati. La frequenza di un grammo permette di calcolare la probabilità che una parola segua un determinato contesto. Grazie a tale probabilità, trattare in modo efficiente collezioni gigantesche di N-grammi hanno diverse applicazioni importanti [Jurafsky, Martin 2014], ad esempio: statistical machine translation, automatic speech recognition, hand-writing recognition, ecc. Esempi pratici che usano strutture dati compresse per accedere alle frequenze dei grammi sono Google Translate e Apple Siri.
Nell’articolo intitolato Efficient Data Structures for Massive N-Gram Datasets [Pibiri, Venturini, SIGIR 2017] dimostriamo come sia possibile indicizzare miliardi di N-grammi in meno della metà dello spazio della migliore soluzione proposta in letteratura e usata nell’industria [Heafield 2011], senza compromettere la velocità di estrazione dei valori associati alle stringhe. I risultato è stato ottenuto proponendo una nuova struttura dati che ha la forma di un trie compresso con Elias-Fano. In particolare, l’articolo propone di codificare l’ultima parola di ogni N-grammo con la posizione che essa occupa nella lista di tutte le parole che posso seguire le precedenti k parole (contesto). Questa nuova tecnica permette di ottenere gli indici più compatti finora posposti in letteratura senza degradare la velocità di accesso.
L’autore ha presentato l’articolo alla conferenza internazionale SIGIR a Tokyo (Giappone) 07/08/2017 - 11/08/2017.
La versione estesa del lavoro [Pibiri, Venturini, TOIS 2019] è stato recentemente accettato dal journal ACM Transactions on Information Systems (2019). Oltre ai risultati già ottenuti, tale versione estesa presenta un nuovo algoritmo per memoria esterna per la stima di grandi language models. Il modello usato prende in nome di Kneser-Ney [Chen and Goodman, 1996] ed è quello più comunemente usato in accademia ed industria. Rispetto allo stato dell’arte [Heafield 2011], l’algoritmo proposto è oltre 4 volte più veloce.
2. Esami sostenuti
Il candidato ha seguito i seguenti esami mentre ospite alla Bertinoro International Spring School (BISS 2016):
• ADVANCED TOPICS IN PROGRAMMING LANGUAGES
• MODELS AND LANGUAGES FOR SERVICE-ORIENTED AND CLOUD COMPUTING • ALGORITHMIC METHODS FOR MINING LARGE GRAPHS
Al dipartimento di Informatica di Pisa, il candidato ha invece seguito i seguenti corsi: • SENSOR NETWORKS, INTERNET OF THINGS AND SMART ENVIRONMENTS • GRAPH MINING ALGORITHMS
3. Seminari
Il candidato ha partecipato ai seguenti cicli di seminari:
• Mauriana Pesaresi Lunchtime Seminars, durante i quali ha presentato il seminario dal titolo: Elias-Fano Encoding: Succinct representation of monotone integer sequences with search operations (1 ora)
• PhD+ Seminars
• Modelling and Analysing Variability in Product Families • Research, Innovation and Future of ICT
4. Soggiorni all’estero
Sono stati effettuati due soggiorni all’estero.
Il primo soggiorno, della durata di 1 mese (dal 01/04/2018 a 01/05/2018), è stato effettuato presso l’istituto di ricerca Riken AIP in Tokyo, Giappone, sotto la supervisione del Dr. Yasuo Tabei.
Il secondo soggiorno, della durata di 5 mesi (dal 01/05/2018 a 01/10/2018), è stato effettuato presso l’Università di Melbourne, Australia, sotto la supervisione di Prof. Alistair Moffat e Dr. Matthias Petri.
6. Riferimenti bibliografici
Peter Elias. Efficient storage and retrieval by content and address of static files. Journal of the ACM, 21(2):246–260, 1974.
Robert Mario Fano. On the number of bits required to implement an associative memory. Memorandum 61, Computer Structures Group, MIT, Cambridge, MA, 1971.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009.
Christopher Manning, Prabhakar Raghavan, and Heinrich Schutze, 2008 Introduction to Information Retrieval. Cambridge University Press.
Alistair Moffat and Lang Stuiver. 2000. Binary Interpolative Coding for Effective Index Compression. Information Retrieval Journal 3, 1 (2000), 25–47.
Giuseppe Ottaviano and Rossano Venturini. 2014. Partitioned Elias-Fano Indexes. In Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 273–282. Stefan Buttcher, Charles Clarke, and Gordon Cormack. 2010. Information retrieval: implementing and evaluating search engines. MIT Press.
Kenneth Heafield. Kenlm: Faster and smaller language model queries. InProceedings of the Sixth Workshop on Statistical Machine Translation, pages 187–197. Association for Computational Linguistics, 2011
Adam Pauls and Dan Klein. Faster and smaller n-gram language models. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 258–267. Association for Computational Linguistics, 2011
Dan Jurafsky and James H Martin. Speech and language processing. Pearson, 2014
Michael L.Fredman and Dan E.Willard Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci., 47(3):424–436, 1993
Mihai Patrascu and Mikkel Thorup. Dynamic integer sets with optimal rank, select, and predecessor search. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 166–175, 2014
Giulio Ermanno Pibiri and Rossano Venturini. Clustered Elias-Fano Indexes. ACM Transactions on Information Systems (TOIS), 36(1):2:1–2:33, 2017.
Giulio Ermanno Pibiri and Rossano Venturini. Dynamic Elias-Fano Representation. In 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland, pages 30:1– 30:14, 2017.
Giulio Ermanno Pibiri and Rossano Venturini. Efficient Data Structures for Massive N-Gram Datasets. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, Shinjuku, Tokyo, Japan, August 7-11, 2017, pages 615–624, 2017.
Giulio Ermanno Pibiri and Rossano Venturini. Variable-Byte Encoding is Now Space-Efficient Too. ArXiv 1804.10949, 2018.
Giulio Ermanno Pibiri and Rossano Venturini. Handling Massive N-Gram Datasets Efficiently. ACM Transactions on Information Systems (2019). To appear.
Giulio Ermanno Pibiri, Matthias Petri, Alistair Moffat. Fast Dictionary-based Compression for Inverted Indexes. In proceedings of the 12th International ACM Conference on Web Search and Data Mining, Melbourne, Australia, February 11-15, 2018.
S. F. Chen and J. Goodman. An empirical study of smoothing techniques for language modeling. In Association for Computational Linguistics (ACL), pages 310–318, 1996.
