Infinity Search：基于 q-度量空间投影的近似向量搜索

arXiv:2506.06557v3 公告类型：replace-cross 摘要：超度量空间或无穷度量空间由一个满足强三角不等式的差异度函数定义，在该不等式中，三角形的任一边都不大于另外两边中较长的一边。我们证明，在超度量空间中使用 vantage point tree 进行搜索时，其最坏情况复杂度等于树的深度。由于所关注的数据集通常并非超度量空间，我们采用一种投影算子，将任意差异度函数转换为超度量空间，同时保留最近邻。我们进一步学习该投影算子的近似形式，以高效计算查询点与数据集中各点之间的超度量距离。随后，我们求解一个更一般的问题，即研究 q-度量空间中的投影——在这类空间中，三角形各边的 q 次幂小于另外两边 q 次幂之和。需要注意的是，使用投影后的 q-度量距离的学习近似，会使搜索流程变为近似搜索。实验表明，增大 q 值可以加快搜索速度，但会降低召回率。总体而言，在 q-度量空间和无穷度量空间中的搜索性能可与现有搜索方法相媲美。