A Scalable and Unified Framework to Weighted Rank Aggregation

measures the ${\mathrm{\ell }}_1$ distance between the position vectors of two permutations:

measures the number of positions where two permutations differ:

The weighted version penalizes mismatches proportionally to the average weight of the mismatched elements:

measures the number of elements pairs $(e,e^{\prime })$ such that the relative order of $e$ and $e^{\prime }$ is reversed between permutations $p$ and $q$. Formally,

where $p^{-1}[e]$ is the position of the element $e$ in the permutation $p$. The weighted version penalizes inversions proportionally to the average weight of the two elements:

measures the minimum number of move operations required to transform one permutation into another, where a move operation removes an element and reinserts it at a different position. We express this using the Indel distance (also known as LCS distance), which counts single-character insertions and deletions. The Indel distance is exactly twice the Ulam distance, since each move corresponds to one deletion followed by one insertion.

In the weighted variant, each insertion or deletion of element $i$ has cost $w(i)$. Thus, the total weighted distance equals the sum of weights of all elements that must be moved to transform one permutation into the other.

Our framework relies on analyzing the geometric structure of the metric space through the following key quantity. For an element $x\in 𝒳$ and a pair $i,j\in [m]$, we consider the triangle inequality slack

This quantity is twice the Gromov product, a fundamental concept in hyperbolic geometry. By the triangle inequality, we have ${\mathrm{\Delta }}_{i,j}(x)\ge 0$ for all $i,j\in [m]$ and $x\in 𝒳$.

Finally, for any subset $Q\subseteq P$, we define the total slack as

While the total slack depends on the set $Q$, we omit $Q$ as it is clear from context, and further denote ${\mathrm{\Delta }}^{\ast }=\mathrm{\Delta }(x^{\ast })$ the total slack of the optimal median. A small total slack of $x$ with respect to $Q$ means that while the points in $Q$ are mutually distant from one another, $x$ serves as an effective median for the entire set. Note that,

It follows that an optimal median of $Q$ minimizes the total slack, and in particular

The inequality holds because $x^{\ast }$, which is optimal for $P$, need not be optimal for the subset $Q$.

Throughout this paper, we assume the input consists of $m$ permutations on $[n]$. In the MPC model [4, 7, 19, 25], both the number of machines and the local memory per machine are required to be significantly smaller than the input size. Accordingly, we fix a parameter , assume each machine has $\widetilde{𝒪}\left(n^{1-ϵ}\right)$ memory¹¹1Throughout, $\widetilde{𝒪}(f)=O(f\cdot \mathrm{polylog}f)$, and aim to minimize the total number of machines used by the algorithm.

An MPC algorithm proceeds in a sequence of rounds. Within each round, every machine performs computations on the data stored in its memory. No communication is allowed during a round; instead, communication occurs only between rounds, with the restriction that the amount of data received by any machine does not exceed its memory capacity. Furthermore, any data output by a machine must be computed solely from the data already present locally. The input data is initially distributed across the machines.

Our general framework operates under the assumption that no point in $P$ achieves cost better than $(2-\alpha )\mathrm{OPT}$ for some constant $\alpha \in (0,1)$. Otherwise, we can achieve a $(2-\alpha )$-approximation by simply returning the minimum-cost point from the input set. With this assumption, the framework relies on two key properties:

Property 1 holds universally for all metric spaces. We prove this through an averaging argument by considering the pairwise distances of points in $P$ and expressing them using the distances from the optimal median $x^{\ast }$. This intuitively suggests that for any two permutations in $Q$, their distance is approximately equal to the sum of their respective distances to the optimal median.

However, Property 2 must be established individually for each metric. When it holds and $y$ is an optimal median of $Q$, Equation (2) implies $\text{dist}(x^{\ast },y)\le 2{\mathrm{\Delta }}^{\ast }$. This means $x^{\ast }$ and $y$ are close, so $y$ serves as a good median for $P$, establishing the local-global property. For local solutions, where $y$ is not optimal median of $Q$, we demonstrate how $\mathrm{\Delta }(y)$ can be bounded in terms of ${\mathrm{\Delta }}^{\ast }$ for our specific metrics. A detailed analysis of our framework is given in Section 2.

Building on the above framework, in Section 3 we present a new approximation algorithm for the 1-median under the Ulam distance, which we later show can be adapted to the MPC setting. For the Ulam metric, we assume that the set $Q$ contains five permutations. A natural baseline approach for computing the $1$-median of the permutations in $Q$ is to apply a dynamic programming algorithm. However, this approach is not space-efficient, as it requires $n^5$ space, which is prohibitive in the MPC setting.

An alternative is to adapt the strategy from [12]. In this approach, an element is called bad if it is not aligned in an optimal alignment between a permutation in $Q$ and the optimal median for at least two permutations in $Q$. Let the bad set denote the collection of all such elements. The algorithm constructs a tournament graph by taking the majority relative order for each pair of elements induced by the permutations in $Q$, then removes cycles and outputs a topological ordering.

The main bottleneck of this approach is the cycle-removal step. In [12], the algorithm repeatedly identifies the shortest cycle and removes all its vertices. Since the graph is a tournament, the shortest cycle always has length three, and it can be shown that at least one vertex in each such triangle must be bad, which allows bounding the number of good elements removed.

However, this approach does not extend to the MPC model. Because no single machine can store an entire permutation, a $3$-cycle $(a,b,c)$ may not be present on any one machine and therefore may go undetected. One possible workaround is to ensure that every triple of elements is collocated on at least one machine. But this leads to further complications: a single element may appear on many machines, and different machines may independently select distinct triangles involving the same vertex (e.g., $(a,b,c)$ and $(a,d,e)$). This is problematic because the [12] analysis crucially relies on the selected cycles being vertex-disjoint in order to bound the number of good elements removed.

It is nontrivial to reconcile these independently detected cycles while maintaining vertex disjointness in the MPC setting. This difficulty forms the main obstacle to implementing prior approaches. To overcome this, we propose a new framework and algorithm that provides a local solution for the permutations in $Q$.

First, fix an optimal median of $Q$, denoted by $y$. We partition $y$ into blocks of length $\kappa =n^{1-\epsilon }$, for some constant $\epsilon >0$. Our goal is to construct, for each such block of $y$, a substring of comparable length that provides a good approximation whenever the objective value of the block is not large. We classify an objective value as large if it is at least $\kappa /\rho$, where $\rho >0$ is a small constant to be specified later. If the objective value is large, we instead use a block consisting only of dummy elements, which already yields a sufficiently good approximation. Furthermore, when approximating a block, we focus only on the good elements and ignore the bad elements. This is valid because the total number of bad elements is small and their cumulative contribution to the objective is large, allowing them to be handled arbitrarily. For this we devise a four-step process.

For each permutation $\pi \in Q$, fix an optimal alignment between $\pi$ and $y$. Let $q$ be a block of $y$. Define $e^{\mathrm{\ell }}\in q$ to be the leftmost element of $q$ that is matched in the optimal alignment between $\pi$ and $y$, and define $e^r\in q$ to be the rightmost element with this property. Suppose $e^{\mathrm{\ell }}$ is matched to $\pi [i]$ and $e^r$ is matched to $\pi [j]$. We define ${\pi }^q$ to be the substring $\pi [i,j]$. The collection of substrings $\{{\pi }^q:\pi \in Q\}$ suffices to reconstruct $q$; we refer to these substrings as the constructive blocks. The main challenge is to identify these constructive blocks efficiently.

We now describe a window decomposition for the permutations in $Q$, beginning with several observations specific to our problem. A key difficulty is that constructive blocks may have highly variable lengths. We first consider the case where at least one constructive block is very large, for example of size greater than $k|q|$ for some sufficiently large constant $k$. In this situation, the objective value of $q$ is already large, and therefore a trivial approximation using a block of dummy elements suffices.

Next, consider the case where at least two constructive blocks are very small. Then many elements of $q$ do not appear in both of these blocks and hence remain unmatched in at least two permutations from $Q$. Such elements are therefore bad elements. This implies that the number of bad elements in $q$ is large. Since the total number of bad elements across all blocks is small, this scenario cannot occur frequently. Consequently, in this case as well, a good approximation can be obtained by using a trivial block consisting only of dummy elements.

From this point onward, we assume that no constructive block is too large and that at most one constructive block is very small. Even under this assumption, the constructive blocks may still have different sizes. To handle this, we introduce a windowing strategy that, for each permutation $\pi \in Q$, generates windows of variable sizes starting at various indices. We ensure that for every constructive block ${\pi }^q$ whose size is neither too large nor too small, there exists a window $\pi [i^{\prime },j^{\prime }]$ such that

where $\mathrm{obj}(q)$ denotes the objective value of the block $q$.

A crucial aspect of this strategy is that we allow windows of size zero to handle very small constructive blocks, and we consider such zero-length windows at multiple starting indices.

Next, using these windows as constructive blocks, we attempt to estimate the blocks of $y$. Since we do not know in advance which windows correspond to a particular block, we try various choices of five windows. Specifically, we form constructive groups by selecting one window from each string in $Q$ using a structured method rather than enumerating all combinations.

Fix an arbitrary choice of five windows (constructive blocks), forming a constructive group. We first construct a graph whose vertices correspond to elements that appear in at least four constructive blocks. This restriction is justified because we only aim to approximate the good elements: any element that does not appear in at least four blocks is classified as a bad element.

For each pair of vertices, corresponding to two elements $c$ and $d$, we orient the edge between them as follows: we add an edge from $c$ to $d$ if $c$ appears before $d$ in at least three of the five blocks, and an edge from $d$ to $c$ if $d$ appears before $c$ in at least three blocks. If neither direction has a strict majority, we add no edge and delete both vertices $c$ and $d$. This is valid because the absence of a majority implies that at least one of $c$ or $d$ is a bad element. Since the total number of bad elements is small, the number of good elements deleted in this process is also small.

After this pruning step, the resulting graph is a tournament. This property is crucial for the next phase, where we remove cycles. We iteratively find the shortest cycle in the graph and delete all vertices in that cycle. Because the graph is a tournament, the shortest cycle has length at most three, and among the vertices of such a cycle, at least one must be a bad element. Moreover, since the cycles removed in different iterations are vertex-disjoint, the total number of good elements deleted remains bounded by the number of bad elements.

Once the graph becomes acyclic, we compute a topological ordering of the remaining vertices, which yields a candidate block for the constructive group. For the subsequent dynamic programming step, we ensure that each candidate block has length at least $\kappa$. Thus, if the string obtained from the topological ordering has length less than $\kappa$, we pad it with dummy elements to reach length $\kappa$.

We combine these candidate blocks, each of length at least $\kappa$, using dynamic programming to obtain a good approximation of $y$. Since the dynamic program operates on blocks, the total state space is polynomial in $n/\kappa =n^{\epsilon }$. Consequently, the DP can be implemented in the MPC setting within a single round by storing all blocks on one machine.

An important subtlety is that, as discussed earlier, for some blocks of $y$ the corresponding constructive blocks may be either very large or very small. In such cases, we approximate the block of $y$ using a block consisting entirely of dummy elements. However, we do not include these dummy-only blocks explicitly in the dynamic program, as doing so would significantly increase the space requirements. Instead, they are handled implicitly within the DP formulation.

The output of the dynamic program is a string that provides a good approximation of $y$ over the good elements. Moreover, each element appears at most once in this string. This property is guaranteed by the construction of the graph used in the previous step, where a vertex corresponding to an element is included only if the element appears in at least four constructive blocks.

The DP output may omit some elements and may include dummy elements As argued earlier, the number of such elements is small and bounded by the number of bad elements. To convert the output into a permutation, we replace each dummy element with a missing element. One simple approach would be to delete all dummy elements and append the missing elements at the end, which would still yield a good approximation. However, our chosen strategy is crucial for enabling an efficient implementation in the MPC setting.

In the element-weighted setting although exact (or almost exact) $1$-median algorithms may exist for computing the median of $Q$, they may not be directly adapted to the massively parallel setting. Such is the case for the rank aggregation problem under Hamming, Spearman’s footrule and Kendall-tau. To this end, we design algorithms that are scalable and are well-suited for implementation in the MPC model

Again, the cornerstone of our approach is to devise a consensus strategy among the permutations in $Q$. We then show that for the relevant $r$, this consensus is close to the optimal median of the entire set $P$. We establish these distance bounds using the total slack term, which provides a unified framework across metric spaces. The details and analysis of the algorithms are presented in Section 4.

Our algorithm constructs a consensus by selecting the majority element at each position where one exists among the three permutations in $Q$. The reasoning for selecting the majority as the basis of our consensus strategy is that if the optimal median does not follow the majority, then both input permutations supporting the majority will differ from the optimum, thereby increasing their slack. Since the total slack is assumed to be small (by Equation 3), this situation cannot occur frequently. Positions without majority agreement are filled arbitrarily with the remaining elements. The key insight is that such positions are exactly those contributing to the total slack: since they lack a majority, they affect both the local solution and the global optimum equally. Importantly, this property holds even in the element-weighted setting, making our consensus strategy robust to weights and yielding a $1.75$-approximation.

We construct a consensus by taking the median element at each position across the three permutations, which yields a pseudo-permutation that may contain duplicates. This consensus is then converted into a valid permutation by sorting the elements and reassigning ranks according to their sorted order. While it is clear that taking the median value at each position minimizes the median cost, it is less obvious that this remains optimal once we enforce the consensus to be a valid permutation.

Our key observation is that whenever the optimal median permutation selects a value different from the position-wise median, the slack increases for at least a pair of inputs. For example, suppose at position $i$ the three input permutations ${\pi }_1,{\pi }_2,{\pi }_3$ have values $a\ge b\ge c$. If the median instead uses some $b^{\prime }\ne b$ (say $b^{\prime }>b$) at index $i$, then the slack of ${\pi }_2$ and ${\pi }_3$ at this position increases by $2(b^{\prime }-b)$. Since the total slack is assumed to be small, such deviations cannot occur frequently. Thus, even under the constraint that the output must be a permutation, taking the position-wise median remains the best consensus strategy. This transformation ultimately yields the closest valid permutation to our consensus under the Spearman’s footrule metric, resulting in an overall $1.75$-approximation.

The Kendall-tau metric compares inversions between pairs of elements. The consensus is determined by majority vote over element pairs rather than positions. We construct a tournament graph where vertex $a$ precedes vertex $b$ if $a$ appears before $b$ in at least two of the three permutations. The resulting feedback arc set problem, solved via the KWIK-SORT algorithm, yields a permutation that respects the majority preference on most pairs. While the KWIK-SORT algorithm was applied to rank aggregation under the Kendall-tau metric in [2] to obtain an approximate 1-median solution, the weighted setting requires a different approach. Using our framework, a weighted tournament is derived from the three input permutations, with edge weights assigned so that the triangle inequality holds, thereby enabling the use of the KWIK-SORT algorithm.

Unlike the previous metrics, consensus under Ulam distance requires subsets $Q$ of size $5$. This follows from a more general property: for any two permutations $x,y$, we show the distance from $x$ to $y$ is at most $\mathrm{\Delta }(x)+\mathrm{\Delta }(y)$. Combined with the universal Property 1, this enables us to improve the metric-specific analysis of [12] and naturally extend the result to the element-weighted variant.

We start by describing how permutations are represented in the MPC model and how pairwise distances are computed, primitives common to all metrics.

A key challenge in the MPC model is that each machine has only $\widetilde{𝒪}(n^{1-\epsilon })$ local memory, which is insufficient to store an entire permutation; consequently, each permutation must be distributed across at least $\widetilde{𝒪}(n^{\epsilon })$ machines. This sublinear memory constraint makes it nontrivial to compute a local solution and validate its cost even for a small subset $Q$ of permutations, necessitating specialized MPC algorithms tailored to different distance metrics. Hamming and Spearman’s footrule distances can be computed in constant rounds using $𝒪\left(n\right)$ total space via block-wise aggregation. Kendall-tau distance requires $n^{2\epsilon }$ machines to handle inversions between all block pairs, resulting in a total of $𝒪\left(n^{1+\epsilon }\right)$ space. Computing Ulam distance in MPC is more challenging, requiring the $(1+\lambda )$-approximation algorithm of [20] with $\widetilde{𝒪}\left(n^{1+\epsilon }\right)$ space.

We address the constraint on total memory through a sampling-based approach. Rather than enumerating all possible candidates, which may be as many as $𝒪\left(m^r\right)$, we show that it suffices to consider only $𝒪\left(\log (n)\right)$ randomly selected input permutations and $𝒪\left(\log (n)\right)$ local solutions derived from $𝒪\left(\log (n)\right)$ random subsets of size $r$. To identify the best candidates, instead of computing their exact costs, we leverage results from [23, 24], which demonstrate that, with high probability, a $(1+\delta )$-approximate solution to the optimal candidate can be found by selecting the permutation with the minimum cost over a random sample of $𝒪\left(\log (n)/{\delta }^2\right)$ input permutations.

Next, we outline how to compute a local solution of the set $Q$ under Ulam, Hamming, Spearman’s footrule, and Kendall-tau distances using constantly many communication rounds.

To employ our new algorithm for the Ulam distance in the MPC setting, we proceed in three phases.

First, we distribute the task of constructing candidate blocks. For each group of five windows, we assign a specific machine to build the tournament graph, remove cycles, and output the resulting block. These results must then be aggregated to find the optimal combination of blocks. A direct approach would be to collect all candidate blocks onto a single machine to run the dynamic programming. However, this is not space-efficient, as the total size of these blocks may exceed the local memory of a single machine. To overcome this, we observe that the dynamic program does not need the actual strings; it only requires their objective values, lengths, and the starting and ending indices of the corresponding windows. This summary information is small enough to fit in the memory of one machine, allowing us to compute the optimal sequence of blocks efficiently.

The solution to the dynamic program implicitly defines a string consisting of $n^{\epsilon }$ blocks. Each block is either a candidate block stored on one of the distributed machines or a logical block consisting entirely of dummy elements. By backtracking through the solution, we can identify the specific machines holding the chosen candidate blocks and assign new machines to generate the required blocks of dummy elements.

It remains to transform this distributed string into a valid permutation of length $n$. We first truncate the string by removing the leftmost dummy elements until the total length is exactly $n$. This is a simple counting task that can be performed using a broadcast tree of constant depth. Next, we must replace each remaining dummy element with a unique unused element. Our strategy is to pair the distinct unused elements with the remaining dummy positions according to their sorted order. That is, the $k$-th smallest unused element should be placed in the $k$-th available dummy position.

To implement this matching, we need to compute the global rank of each unused element and each dummy position. Since the data is distributed, each machine first counts the unused elements it holds locally. Then, using a broadcast tree, each machine computes the total count of unused elements residing on all preceding machines. This allows every machine to determine the exact global rank of its elements. We apply the same procedure to rank the dummy positions. Finally, the elements and positions with matching ranks are routed to the same machine to complete the permutation.

In the algorithm for Hamming distance, (i) a majority element is assigned to each position if it exists among the permutations in $Q$. (ii) Positions without majority agreement are filled arbitrarily with remaining elements. The first step can be simulated in MPC similar to computing the Hamming distance: we bring the information from the $i$’th block of each permutation in $Q$ to a single machine and decide the majority.

The difficulty lies in the second step, as the list of unused elements and unassigned positions can be large and may not fit in a single machine. A simple approach is to assign unused elements in each $i$ block to unassigned positions in the same block. However, this may not be feasible as the number of unused elements and unassigned positions in a block may differ. To resolve this, we consider the sorted list of unused elements and unassigned positions, and aim to pair them according to their order in the sorted lists. This requires computing the rank of each unused element relative to all unused elements, and the rank of each unassigned position relative to all unassigned positions. To implement this, we let each $i$’th machine keep the unused elements in the $i$’th block. The rank of each element can be computed if each machine knows the number of unused elements in all the previous blocks. This information can be made available to all machines by using a broadcast tree of depth $\max (1,\frac{2\epsilon -1}{1-\epsilon })$. We proceed similarly for unassigned positions. Finally, the elements and positions with the same rank are sent to the same machine.

In the algorithm for Spearman’s footrule distance, we first compute a pseudo-permutation by assigning the median element at each position across the permutations in $Q$. The output permutation is obtained by sorting the elements in the pseudo-permutation and reassigning ranks according to their sorted order. The first step can be implemented in MPC similar to Hamming distance. The second step pose a similar challenge as in Hamming distance, since the elements are distributed across multiple machines. By sorting all elements in the pseudo-permutation, we reduce this problem to the pairing problem as in Hamming distance.

For Kendall-tau distance, recall that we need to apply the KWIK-SORT algorithm to solve the feedback arc set problem on the majority graph induced by $Q$. The KWIK-SORT algorithm starts with a random vertex as pivot, and partitions the remaining vertices into two sets according to the direction of the edges between them and the pivot. We then recurse on the two sets, and concatenate the results. We follow a constant rounds MPC implementation of KWIK-SORT presented in [22]. The approach to simulate this in constant MPC rounds is to pick multiple pivots in each round. These pivots form a decision tree, which partitions the vertices into multiple sets. We then recurse on each set in parallel. However, if we directly follow the algorithm in [22], we will violate the local space constraint. In particular, [22] allows the local space to be $\widetilde{𝒪}\left(n\right)$, hence, they can choose $𝒪\left(n^{1/2}\right)$ pivots simultaneously in each round. Our local space may not be sufficient to accommodate this many vertices. We overcome this by choosing only $𝒪\left(n^{1-\epsilon }\right)$ vertices as pivots. Due to the fact that the size of partitioned sets can not be too large [22, Lemma 7], as long as the number of pivots is $\mathrm{\Omega }(\log (n))$, the number of rounds remains constant. Another challenge is that in [22], the total space is $𝒪\left(n^2\right)$, as they need to store the edges explicitly. We resolve this by observing that we can access the direction of an edge by accessing the positions of two elements in the permutations in $Q$. This allows us to store the edges implicitly, keeping the total space at $𝒪\left(n\right)$.