The data structure at the core of large-scale search engines is the inverted index, which is essentially a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by such engines and stringent performance requirements imposed by the heavy load of queries, the inverted index stores billions of integers that must be searched efficiently. In this scenario, index compression is essential because it leads to a better exploitation of the computer memory hierarchy for faster query processing and, at the same time, allows reducing the number of storage machines. The aim of this article is twofold: first, surveying the encoding algorithms suitable for inverted index compression and, second, characterizing the performance of the inverted index through experimentation.
Techniques for inverted index compression
Pibiri GE;
2020
Abstract
The data structure at the core of large-scale search engines is the inverted index, which is essentially a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by such engines and stringent performance requirements imposed by the heavy load of queries, the inverted index stores billions of integers that must be searched efficiently. In this scenario, index compression is essential because it leads to a better exploitation of the computer memory hierarchy for faster query processing and, at the same time, allows reducing the number of storage machines. The aim of this article is twofold: first, surveying the encoding algorithms suitable for inverted index compression and, second, characterizing the performance of the inverted index through experimentation.File | Dimensione | Formato | |
---|---|---|---|
prod_435494-doc_157072.pdf
accesso aperto
Descrizione: Techniques for Inverted Index Compression
Tipologia:
Versione Editoriale (PDF)
Dimensione
2.88 MB
Formato
Adobe PDF
|
2.88 MB | Adobe PDF | Visualizza/Apri |
prod_435494-doc_164483.pdf
non disponibili
Descrizione: Techniques for Inverted Index Compression
Tipologia:
Versione Editoriale (PDF)
Dimensione
999.77 kB
Formato
Adobe PDF
|
999.77 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.