[Paper Reading] DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph

type

status

date

slug

summary

背景

随着多模态数据（如图像-文本、视频-文本、地理位置-文本等）的普及，混合向量查询 （Hybrid Vector Search）成为研究热点。这类查询通常涉及两个或多个向量，通过加权和的方式计算相似度。例如，用户在寻找“附近的日料店”时，既关心地理位置，也关心语义匹配程度。

Research Gap & Challenges

现有方法在构建index时假设距离是固定的，然而在混合查询中，权重是可变的，导致一个索引结构在不同下性能表现不同，在某些情况性能严重下降。

Challenges：

Candidate neighbors难以确定：变化时，距离度量也会变化，每个节点的最近邻也会随之变化。对每个节点来说，要如何构建一个对所有都有效的neighbor候选集？

剪枝策略失效：RNG（构建graph-based index常用的剪枝策略）依赖于边长度进行剪枝，而的变化会导致这种策略失效。

搜索起点难以选择：图的中心点会随变化，无法对任意都给出很好的start node。

问题定义

Similarity计算

：个物体的数据集。每个object有两个feature vectors，和。给定一个query ，为可调参数，控制对两种feature vector的倾向程度，两个物体的hybrid distance计算如下。

其中以及，计算与两个向量之间的欧式距离，和。做这种归一化是因为当两个向量数值尺度不一样的情况下，直接算距离会导致数值大的模块完全主导hybrid distance，使得失去意义。

Problem Statement

HVQ：给定一个query ，hybrid vector query意图找到与具有最小hybrid distance的个物体。

这篇文章的目标是：构建一个graph-based ANNS index使得在不同的权重上，搜索算法都能表现良好（effective and efficient）。

方法

方法总览

和原始文章的结构不同，我们这里先看看他们方法的总体框架，再讨论每个部分的细节。

我们先初始化这个要构建的graph ，它只包含一个点，其中是通过Edge seed方法选出来的初始点。随后对中的每个点，我们先通过GPS算法选出合适的候选集，随后再通过提出的新剪枝方法DRNGPrune，从候选集中选出真正的neighbor。随后，对于的每个邻居，再应用一次DRNGPrune剪枝掉多余的边。最后更新下一轮的start node。

接下来我们详细讲GPS（即确定candidate set）和DRNGPrune（确定最终neighbor，精简graph）算法。