We revisit the Bipartite Graph Partitioning approach to document reordering (Dhulipala et al., KDD 2016), and consider a range of algorithmic and heuristic refinements that lead to faster computation of index-minimizing document orderings. Our final implementation executes approximately four times faster than the reference implementation we commence with, and obtains the same, or slightly better, compression effectiveness on three large text collections.
Errata: The journal entry for reference [22] (Pibiri and Venturini) should be “ACM Computing Surveys”, not “ACM Transactions on Information Systems” as listed in the paper.