小红书精读：Efficient Swing Computation for Retrieval in Large-Scale Recommender Systems

Swing检索提速千倍，只要近似

各位算法同学们，先甩个数字：十亿边的图做 top-100 Swing 查询，精确方法要 8.5 秒，这篇 K-ASC 只要 1.5 毫秒，平均精度还超过 99.9%。Swing 是阿里、快手、Shopee 都在用的 i2i 召回相似度，但它的计算复杂度是查询物品度数的平方，热门物品挂几万个用户，一次查询就要枚举上亿对用户，这篇工作就是来拆这个开销的。

📄 Efficient Swing Computation for Retrieval in Large-Scale Recommender Systems

🔧 把问题重定义成 (ε, λ) 近似 Swing 查询：Swing 值高于阈值 λ 时给相对误差 ε，低于 λ 只要求 ε·λ 的绝对误差，不是所有目标物品都要算准，误差边界写得很清楚。 🧩 ASC 把 GNS 和 USS 两个随机估计器拼到一起：GNS 用分组去掉重复的用户对交集，USS 干脆不做交集、只估基数，再按代价模型自适应地给高/低度数查询物品选估计器。 ⚙️ K-ASC 走 filter-refinement：先用一部分采样预算粗估候选、维护上下界，挑出 top-K 候选和边界物品，再把剩余预算全砸在边界物品上细化排序，配合位图剪枝。

📊 8 个真实数据集上，达到同样的 (ε, λ) 近似保证或相当的 top-K 排名精度时，ASC 和 K-ASC 的计算时间比精确法和 Monte-Carlo 基线快几个数量级。 📈 最大的 MAG 图上，K-ASC 做 top-100 查询平均精度超过 99.9%，耗时 1.5 毫秒，精确方法要 8.5 秒。 ✅ 亿级边的 Yambda 和 MAG 上 K-ASC 仍然跑得动，不只是中等规模图上的结果。

总结感想：如果你的 i2i 召回就是 Swing，被热门物品的度数卡住，或者现在靠截断用户数硬扛，这篇的误差定义和 filter-refinement 可以直接对标，重点看你在意的 λ 处精度掉多少、P99 延迟能压到哪。坑有两个：一是它给的是概率误差保证，ε、λ、δ 得跟着线上召回质量调；二是 GNS/USS 的切换依赖代价模型里的经验参数 ρ，换数据集先校准，不然自适应可能选错估计器。

原文：AlphaXiv