When Greedy Is Sorting: Exact and Certified Ideal Rankings for Novelty Metrics
Kehan Liu, Zhaoyun Chen, Xianquan Yan
原文摘要
The ideal ranking that normalizes novelty metrics is NP-hard to compute in general, so widely used $α$-nDCG evaluators approximate its denominator with a greedy rule that rescans every remaining document at each rank. We identify a regime in which this ideal ranking is exact and cheap for both $α$-DCG and intent-aware expected reciprocal rank (ERR-IA). When each document is positively judged for at most one intent, each metric reduces to the classical allocation of a fixed budget across chains of decreasing marginal gains. A metric-specific virtual-score transformation followed by a multiway merge, which we call ChainMerge, returns the globally optimal top-$K$ ranking in $O(G+K\log G)$ time from $G$ preordered intent groups, or in $O(n+K\log G)$ time from $n$ globally preordered candidates, instead of the $Θ(nK)$ of the greedy rule. When intent judgments overlap, exact $α$-DCG optimization is NP-hard under the standard logarithmic discount and $α=0.5$, even when every document has three intents and every intent occurs in two documents. For arbitrary overlap, a polynomial-size LP over nested ranking prefixes upper-bounds the ideal score and certifies the optimality gap of any feasible ranking. In the official TREC Web 2009-2012 judgments, 64.8% of positive documents serve a single intent, yet only 20 of 198 complete queries do so throughout. Beyond this exact regime, the LP certifies 189 of the 198 greedy denominators as globally optimal, and the resulting score intervals preserve the winner in all eight matched comparison groups. On 65,238 MIND-small candidates, ChainMerge returns identical optimal objectives 17-1,011 times faster than the greedy rule. For $α$-DCG, these results trace the hardness of the ideal ranking to intent overlap.
cs.IR