Document identifier reassignment and run-length-compressed inverted indexes for improved search performance
Document identifier reassignment and run-length-compressed inverted indexes for improved search performance
复制标题
文档标识符重新分配和游程压缩倒排索引可提高搜索性能
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Victor Sepulveda
中科院分区：
文献类型：
--
作者：
Diego Arroyuelo;Senén González;M. Oyarzún;Victor Sepulveda
文本搜索引擎是当今最基本的工具。它们的效率依赖于一种流行而简单的数据结构：倒排索引。目前，使用索引压缩方案可以非常有效地表示倒排索引。最近的调查还研究了如何优化的文档排序可以用来分配文档标识符（docID）的文档数据库。这在索引压缩和查询处理时间方面产生了重要的改进。在本文中，我们遵循这一研究路线，但从不同的角度。我们提出了一个docID重新分配方法，允许一个专注于一个给定的倒排列表的子集，以提高其性能。然后，我们使用行程编码来压缩这些列表（因为会生成许多连续的1）。我们表明，通过使用这种方法，不仅提高了特定的倒排列表的子集的性能，而且整个倒排索引。我们的实验结果表明，减少约10%的空间使用的整个索引docID重新分配的重点。此外，如果运行必须显式解压缩，解压缩速度最高可快1.22倍，如果允许运行的隐式解压缩，解压缩速度最高可快4.58倍。最后，我们还改进了AND查询（最多12%），WAND查询（最多23%）和完整（非排名）OR查询（最多86%）的Document-at-a-Time查询处理时间。
Text search engines are a fundamental tool nowadays. Their efficiency relies on a popular and simple data structure: the inverted indexes. Currently, inverted indexes can be represented very efficiently using index compression schemes. Recent investigations also study how an optimized document ordering can be used to assign document identifiers (docIDs) to the document database. This yields important improvements in index compression and query processing time. In this paper we follow this line of research, yet from a different perspective. We propose a docID reassignment method that allows one to focus on a given subset of inverted lists to improve their performance. We then use run-length encoding to compress these lists (as many consecutive 1s are generated). We show that by using this approach, not only the performance of the particular subset of inverted lists is improved, but also that of the whole inverted index. Our experimental results indicate a reduction of about 10% in the space usage of the whole index docID reassignment was focused. Also, decompression speed is up to 1.22 times faster if the runs must be explicitly decompressed and up to 4.58 times faster if implicit decompression of runs is allowed. Finally, we also improve the Document-at-a-Time query processing time of AND queries (by up to 12%), WAND queries (by up to 23%) and full (non-ranked) OR queries (by up to 86%).