arXiv:2504.14861cs.DBcs.IR2025-04中稿 · SIGIR 2025被引 5

融合内积与欧氏距离,提升高维数据搜索效率。

Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search

  • 设计新型图索引MAG,动态切换内积与欧氏度量进行搜索。
  • 在12个真实数据集上实现最高4倍加速,保持精度稳定。
  • 提出三个拓扑指标,指导参数调优,适合大规模检索场景。

最大内积搜索(MIPS)是机器学习与信息检索中的基础挑战,尤其在高维数据应用中。现有方法或仅依赖内积相似性,存在局部最优和冗余计算问题;或通过空间投影将MIPS转化为欧氏最近邻搜索,导致拓扑破坏与信息丢失。本文认为内积与欧氏度量并非对立,通过协同设计索引与搜索算法可显著提升性能。基于图搜索框架,我们揭示不同策略对数据拓扑的适应性差异。据此提出新型图索引Metric-Amphibious Graph(MAG)及自适应度量切换搜索算法ANMS。为辅助参数调优,我们识别出三个强关联数据拓扑特性的统计指标。在12个真实数据集上的实验表明,MAG优于现有最先进方法,实现最高4倍搜索速度提升,兼具适应性与可扩展性。

原文摘要 · Abstract (English)

Maximum Inner Product Search (MIPS) is a fundamental challenge in machine learning and information retrieval, particularly in high-dimensional data applications. Existing approaches to MIPS either rely solely on Inner Product (IP) similarity, which faces issues with local optima and redundant computations, or reduce the MIPS problem to the Nearest Neighbor Search under the Euclidean metric via space projection, leading to topology destruction and information loss. Despite the divergence of the two paradigms, we argue that there is no inherent binary opposition between IP and Euclidean metrics. By stitching IP and Euclidean in the design of indexing and search algorithms, we can significantly enhance MIPS performance. Specifically, this paper explores the theoretical and empirical connections between these two metrics from the MIPS perspective. Our investigation, grounded in graph-based search, reveals that different indexing and search strategies offer distinct advantages for MIPS, depending on the underlying data topology. Building on these insights, we introduce a novel graph-based index called Metric-Amphibious Graph (MAG) and a corresponding search algorithm, Adaptive Navigation with Metric Switch (ANMS). To facilitate parameter tuning for optimal performance, we identify three statistical indicators that capture essential data topology properties and correlate strongly with parameter tuning. Extensive experiments on 12 real-world datasets demonstrate that MAG outperforms existing state-of-the-art methods, achieving up to 4x search speedup while maintaining adaptability and scalability.

MIPS图索引度量学习高维搜索

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。