The data structure at the core of nowadays large-scale search engines, social networks and storage architectures is the inverted index, which can be regarded as being a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by search engines and stringent performance requirements dictated by the heavy load of user queries, the inverted lists often store several million (even billion) of integers and must be searched efficiently. In this scenario, compressing the inverted lists of the index appears as a mandatory design phase since it can introduce a twofold advantage over a non-compressed representation: feed faster memory levels with more data in order to speed up the query processing algorithms and reduce the number of storage machines needed to host the whole index. The scope of the chapter is the one of surveying the most important encoding algorithms developed for efficient inverted index compression.
Inverted Index Compression
Pibiri GE;Venturini R
2018
Abstract
The data structure at the core of nowadays large-scale search engines, social networks and storage architectures is the inverted index, which can be regarded as being a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by search engines and stringent performance requirements dictated by the heavy load of user queries, the inverted lists often store several million (even billion) of integers and must be searched efficiently. In this scenario, compressing the inverted lists of the index appears as a mandatory design phase since it can introduce a twofold advantage over a non-compressed representation: feed faster memory levels with more data in order to speed up the query processing algorithms and reduce the number of storage machines needed to host the whole index. The scope of the chapter is the one of surveying the most important encoding algorithms developed for efficient inverted index compression.File | Dimensione | Formato | |
---|---|---|---|
prod_402786-doc_140166.pdf
solo utenti autorizzati
Descrizione: Inverted Index Compression
Tipologia:
Versione Editoriale (PDF)
Dimensione
455.18 kB
Formato
Adobe PDF
|
455.18 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
prod_402786-doc_140200.pdf
accesso aperto
Descrizione: Inverted Index Compression
Tipologia:
Versione Editoriale (PDF)
Dimensione
413.2 kB
Formato
Adobe PDF
|
413.2 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.