Faster Index Reordering with Bipartite Graph Partitioning

Abstract

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.

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