标题：HQANN：结构和非结构条件限制查询下的高效稳定的相似性搜索

编者的总结

• 本文设计了标量属性的距离公式，和向量距离做加权和，引入到了图索引里面。

编者的思考

1. 这种混合式索引似乎限制了查询时标量属性的个数，比如一共有20个属性，但查询的限制条件只有2个，那就没法用了，因为即使这2个限制条件都满足的节点互相之间也没有连边，不在一个neighborhood里面。这是一个比较强的限制。
2. 第二个问题在于标量距离的设计，即使在生产环境中，属性全为整数的限制也太强了，浮点数、字符串都是经常出现的标量属性。而且，如何协调不同属性的距离Scale也是个问题，比如性别的0和1，距离只可能是0和1，但年龄之间的差距就会很大，距离也很大，如果不做特别的设计，对于不同的属性实际上产生了不同的重要性偏好。
3. 总的来看，标量的查询是一种离散空间上的查询，向量相似度查询是连续空间上的查询，将这两个协调统一起来并不容易，且尚不清楚是否合适。

1 INTRODUCTION

• 本文针对的问题是标量和向量的联合查询，即在一些常规标量属性限制条件下的向量kNN检索。举个例子，推荐（向量）离我10公里以内（标量），现在开业的（标量）餐厅。
• 具体的做法是将标量查询条件混进向量距离定义里面，使得向量索引中的距离就包含着标量的含义。
• 现有工作的模式无外乎以下三种：
  1. 先搜向量（多准备一下），然后用标量条件过滤；（比如Vearch）
     • 这种方法的问题在于不知道提前要多搜多少向量，搜多少也有可能不满足后面的标量条件导致查询失败。
  2. 先搜标量过滤缩小查询范围，然后查询向量；（比如ADBV，在第一步准备一个bitmap用以辅助向量查询；再比如Milvus，会按照标量属性分区，）
     • 这种方法的问题在于延迟较高。
  3. 混合距离，直接在一个索引中查询。（比如NHQ，以及本文的HQANN）
     • 作者认为NHQ把向量查询放在主要的位置上是不对的，标量的重要性应该更大，所以NHQ在标量属性较多时性能有下降。

image.png

3 HQANN

本文的方法就是混合了标量和向量的距离，具体来说就是加权和的形式。

image.png

向量距离g很正常，关键是标量距离f如何设计。

• 如下式，两个标量完全相等则距离为0，否则会有一个很大的距离，即bias。如果有部分属性相同则适当减小距离。

• 标量之间的基本距离按照一范数曼哈顿距离设计的，但作者称用其他范数也没问题。

  
  image.png
• 作者称生产环境中的属性都是整数值，因此在两个节点的最小标量距离是1.
  【编者将大偏移的后面一项画了出来，基本上是个指数递增，不过在bias面前都是微调】
• 由于这个巨大的bias，标量的重要性被放的很大。

image.png

• 查询时要首先通过路由找到标量属性满足条件的点，然后搜索其neighborhood.

4 EXPERIMENTS

• 从作者的实验看，Milvus和ADB-V这种先过滤再走向量查的索引性能上都一般，主要是有些慢；

• Vearch这种先查向量的在高召回段性能下降明显。

  
  image.png
  image.png