用户名密码登录

论文题目：GraSP: Optimizing Graph-based Nearest Neighbor Search with Subgraph Sampling and Pruning

1. 发现

• 作者统计了HNSW算法的边在查询时被访问的频率，发现在查询过程中极少数的边被高频地访问。这说明在查询过程中有些节点担任“枢纽节点“的角色，枢纽节点连接的边会被高频访问。其他的节点在重要性上较为边缘，他们的边访问次数很低。
• 作者还分析认为，目前的图构建方法中所有节点设置统一的邻居数。邻居数大了搜索路径变短但距离比较时间变长；邻居数小了则反之。因此如何设置邻居数量需要权衡。这里作者认为，不需要所有节点都有统一的邻居数量，可以让图自适应的决定节点的邻居数量，让“枢纽节点”多连一些边，边缘节点少连一些边，在边缘节点上不用花太多时间进行距离比较，在枢纽节点进行精确的比较从而更精准地定位搜索方向，以达到搜索效率的提升。

2. 方法

2.1 近邻图概率模型

• 给近邻图中的边添加上权重，根据权重可计算一个概率，并可根据概率值评判此边是去是留（伯努利随机变量）。初始时，各边的概率相等

2.2 迭代方法

1. 按照边的初始概率随机删除一些边，得到一个新的子图；
2. 在原图和子图上分别进行相同的搜索，比较搜索结果，衡量搜索差距
3. 根据搜索差距的大小，调整边的重要性程度。比如，如果误差大，则提升相应边的权重；
4. 重复上述过程进行迭代，最终各边获得合适的权重。删掉权重低的边，保留权重大的边，得到子图。在该子图上执行搜索。### 论文题目：GraSP: Optimizing Graph-based Nearest Neighbor Search with Subgraph Sampling and Pruning

1. 发现

• 作者统计了HNSW算法的边在查询时被访问的频率，发现在查询过程中极少数的边被高频地访问。这说明在查询过程中有些节点担任“枢纽节点“的角色，枢纽节点连接的边会被高频访问。其他的节点在重要性上较为边缘，他们的边访问次数很低。
• 作者还分析认为，目前的图构建方法中所有节点设置统一的邻居数。邻居数大了搜索路径变短但距离比较时间变长；邻居数小了则反之。因此如何设置邻居数量需要权衡。这里作者认为，不需要所有节点都有统一的邻居数量，可以让图自适应的决定节点的邻居数量，让“枢纽节点”多连一些边，边缘节点少连一些边，在边缘节点上不用花太多时间进行距离比较，在枢纽节点进行精确的比较从而更精准地定位搜索方向，以达到搜索效率的提升。

2. 方法

2.1 近邻图概率模型

• 给近邻图中的边添加上权重，根据权重可计算一个概率，并可根据概率值评判此边是去是留（伯努利随机变量）。初始时，各边的概率相等

2.2 迭代方法

1. 按照边的初始概率随机删除一些边，得到一个新的子图；
2. 在原图和子图上分别进行相同的搜索，比较搜索结果，衡量搜索差距
3. 根据搜索差距的大小，调整边的重要性程度。比如，如果误差大，则提升相应边的权重；
4. 重复上述过程进行迭代，最终各边获得合适的权重。删掉权重低的边，保留权重大的边，得到子图。在该子图上执行搜索。