Faster Index Reordering with Bipartite Graph Partitioning


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.

Proceedings of the 44th International ACM Conference on Research and Development in Information Retrieval (SIGIR 2021)

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.