Efficient dynamic rank aggregation

doi:10.1108/ijwis-07-2025-0190

Return

Efficient dynamic rank aggregation

2026-04-01

PRE

Alimi, Morteza *

Mehrabiun, Hourieh

Alireza Zarei

DOI：10.1108/ijwis-07-2025-0190

Original

Original request for help

Save

Abstract

En 中文

PurposeThe 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.Design/methodology/approachThe 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.FindingsExperimental 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.Originality/valueTo 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.

Keywords:

Approximation algorithm

Dynamic algorithm

Dynamic rank aggregation

Optimal footrule aggregation