Conference Proceedings

Compressing inverted indexes with recursive graph bisection: A reproducibility study

J Mackenzie, A Mallia, M Petri, JS Culpepper, T Suel

Lecture Notes in Artificial Intelligence | Springer | Published : 2019


© Springer Nature Switzerland AG 2019. 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 algorith..

View full abstract


Awarded by Australian Research Council

Funding Acknowledgements

This work was supported by the National Science Foundation (IIS-1718680), the Australian Research Council (DP170102231), and the Australian Government (RTP Scholarship).