Compressing Inverted Indexes with Recursive Graph Bisection: A Reproducibility Study
Compressing Inverted Indexes with Recursive Graph Bisection: A Reproducibility Study
复制标题
DOI：
10.1007/978-3-030-15712-8_22
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
J. Mackenzie;Antonio Mallia;M. Petri;J. Culpepper;Torsten Suel
中科院分区：
文献类型：
--
作者：
J. Mackenzie;Antonio Mallia;M. Petri;J. Culpepper;Torsten Suel
文档重新排序是索引构建中一个重要但经常被忽视的预处理阶段。在图和倒排索引中重新排序文档标识符已被证明可以降低存储成本并提高结果索引的处理效率。然而，令人惊讶的是，很少有文档重新排序算法是公开的，尽管它们的重要性。Dhulipala等人最近提出了一种新的基于递归图二分的重排序算法，并且当与其它现有技术的重排序策略相比时显示出高度有效和高效。在这项工作中，我们提出了一种新的算法的再现性研究。我们描述的实施遇到的挑战，并探讨我们的洁净室重新实施的性能特点。我们表明，我们能够成功地再现原始论文的核心结果，并表明该算法推广到其他集合和索引框架。此外，我们公开了我们的实施，以帮助促进这一领域的进一步研究。
Document reordering is an important but often overlooked preprocessing stage in index construction. Reordering document identifiers in graphs and inverted indexes has been shown to reduce storage costs and improve processing efficiency in the resulting indexes. However, surprisingly few document reordering algorithms are publicly available despite their importance. A new reordering algorithm derived from recursive graph bisection was recently proposed by Dhulipala et al., and shown to be highly effective and efficient when compared against other state-of-the-art reordering strategies. In this work, we present a reproducibility study of this new algorithm. We describe the implementation challenges encountered, and explore the performance characteristics of our clean-room reimplementation. We show that we are able to successfully reproduce the core results of the original paper, and show that the algorithm generalizes to other collections and indexing frameworks. Furthermore, we make our implementation publicly available to help promote further research in this space.