Techniques for Inverted Index Compression
Techniques for Inverted Index Compression
复制标题
DOI：
10.1145/3415148
复制
发表时间：
2021-02-01
影响因子：
16.6
通讯作者：
Venturini, Rossano
中科院分区：
文献类型：
--
作者：
Pibiri, Giulio Ermanno;Venturini, Rossano
大规模搜索引擎的核心数据结构是倒排索引，它本质上是一个被称为倒排列表的排序整数序列的集合。由于此类引擎索引了许多文档，并且繁重的查询负载带来了严格的性能要求，因此倒排索引存储了数十亿个必须高效搜索的整数。在这个场景中，索引压缩是必不可少的，因为它可以更好地利用计算机内存层次结构来实现更快的查询处理，同时还可以减少存储机器的数量。本文的目的有两个：首先，研究适用于倒排索引压缩的编码算法；其次，通过实验来表征倒排索引的性能。
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.