标题：优化基于图的近似最近邻搜索：更强更智能

编者的总结

1. 本文观察到插入时入边较少决定了最终点的入度也会少，会更难被检索到，于是提出从candidate set中选一些补充进反向边。有不到10%的速度提升。
2. 另一个贡献是查询时间长尾分布和early termination，可惜21'sigmod已经有文章做过了。
3. 此外还有一些比较有趣的发现：
   • efSearch和搜索步数有很强的正比关系，而且绝对值上相差也很小。
   • 改变数据集的索引插入顺序，同样一批query的难度相差非常大。
4. 方法的技术深度有限，有观察，但缺一些创新性。

Abstract & Introduction

现有图的问题：

• 连通性差：主要体现在一部分点的入度很低，不容易查得到；
• 冗余搜索：即搜索步数是长尾分布的；

本文的方法：

• 增强反向连接（stronger）：新插入的点增大入度，出度不变；
• early ternmination search (smarter)

III. REVERSE CONNECTION ENHANCEMENT

A. Motivation

大抵的意思是入度越低，精度损失越大，但这图的意思不太清楚；

image.png

B. Degree Analysis

构建时如果某个边反向边连的越少，那么建成图之后他的入度也是较小的，反之亦然。
而构建时反相边连接的条数的上界就是出边的个数，这就限制了一般的

image.png

C. Our Method

每次加反相边时，从插入点的candidates （efCons个）中选一些无法到达插入点的补一些反相边。