The rank aggregation problem, which has many real-world applications, refers to combining multiple input rankings into a single aggregated ranking. In dynamic settings, where new rankings arrive over time, efficiently updating the aggregated ranking is essential. This paper aims to develop fast, theoretically grounded and practically efficient algorithms for dynamic rank aggregation.
The authors first develop left right (LR) aggregation, built on the LR tree data structure. The LR tree is inspired by the LR distance, a novel but equivalent formulation of the classical Spearman’s footrule distance, designed to support efficient incremental updates. They then analyze the classical Pick-A-Perm algorithm under Spearman’s footrule distance and show how it can also be maintained efficiently in the dynamic setting. Finally, they combine LR aggregation and Pick-A-Perm into a unified dynamic rank aggregation framework that returns the better of the two candidate aggregations at each step.
Experimental evaluations show that LR aggregation produces solutions close to optimal in practice. They prove that Pick-A-Perm yields an expected 2-approximation under Spearman’s footrule distance and they show that both LR aggregation and Pick-A-Perm (as well as their combination) can be implemented with O (n log n) update time and O(n2) space, independent of the number of rankings received.
To the best of the authors’ knowledge, this work provides the first near-linear-time dynamic rank aggregation framework that offers both a provable approximation guarantee and strong empirical performance in practice.
