标题： 高效动态排名聚合 显示英文标题

标题： Efficient Dynamic Rank Aggregation

摘要： 排名聚合问题具有许多实际应用，指的是将多个输入排名合并为一个聚合排名的过程。 在动态环境中，随着新排名随时间到达，高效地更新聚合排名是必不可少的。 本文开发了一种快速、理论和实践上高效的动态排名聚合算法。 首先，我们开发了LR-Aggregation算法，该算法基于LR树数据结构，而LR树本身是基于LR距离构建的，这是一种新颖且等价于经典Spearman脚尺距离的方法。 然后，我们分析了Pick-A-Perm算法的理论效率，并展示了如何使用我们开发的另一种数据结构将其与LR聚合算法结合。 通过实验评估，我们证明了LR-Aggregation在实践中可以产生接近最优的解决方案。 我们证明了Pick-A-Perm在理论上最坏情况下的近似保证为2。 我们还证明了LR-Aggregation和Pick-A-Perm算法，以及它们的结合方法都可以在$O(n \log n)$时间内运行。 据我们所知，这是第一个在动态设置中快速、接近线性时间的排名聚合算法，它同时具有理论上的近似保证和出色的实践性能（远优于理论保证）。 显示英文摘要

摘要： The rank aggregation problem, which has many real-world applications, refers to the process of 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 develops a fast, theoretically and practically efficient dynamic rank aggregation algorithm. First, we develop the LR-Aggregation algorithm, built on top of the LR-tree data structure, which is itself modeled on the LR-distance, a novel and equivalent take on the classical Spearman's footrule distance. We then analyze the theoretical efficiency of the Pick-A-Perm algorithm, and show how it can be combined with the LR-aggregation algorithm using another data structure that we develop. We demonstrate through experimental evaluations that LR-Aggregation produces close to optimal solutions in practice. We show that Pick-A-Perm has a theoretical worst case approximation guarantee of 2. We also show that both the LR-Aggregation and Pick-A-Perm algorithms, as well as the methodology for combining them can be run in $O(n \log n)$ time. To the best of our knowledge, this is the first fast, near linear time rank aggregation algorithm in the dynamic setting, having both a theoretical approximation guarantee, and excellent practical performance (much better than the theoretical guarantee).