1.备战SISAP 2025挑战：调研2024挑战

简介

紧张刺激的SISAP 2025 challenge发布了，此博客用于记录备战的一些准备，思路和实验。

25年挑战介绍

详细信息参考SISAP Indexing challenge 2025

Task 1：内存受限索引

这项任务要求参与者开发具有reranking（重排，就是说保证knn结果是有序的）功能的内存高效索引解决方案。每个解决方案都将在内存和存储资源有限的Linux容器中运行。

• 容器限制：8个虚拟CPU，16GB运存，数据库只读（意味着容器内的程序可以访问并读取数据集，但无法对数据进行任何修改或写入操作）
• 整个任务（包括构建和测试）时间限制：12小时
• 最小平均召回率要求：0.7
• 数据集：PUBMED23 (2300 万个384维向量) with out-of-distribution queries （测试时的查询数据不服从数据集的分布，不是从数据集中采样的）
• 目标：找到每个查询对象的 k=30 个最近邻
  • 用在16个不同搜索超参数上得到的最佳吞吐量衡量每个团队的最终得分。（满足基本要求后比的是吞吐量/效率）
  • 提供11,000个查询目标用于开发、测试
  • 最终提交评估用的是10,000个新的查询目标

Task 2：K-NN图构建（也称为 metric self-join 度量自连接）

在这项任务中，参与者被要求开发内存高效的索引解决方案构建出k=15的k近邻图。每个解决方案都将在内存和存储资源有限的Linux容器中运行。

• 容器限制：8个虚拟CPU（应该可以看作8核，不考虑超线程），16GB运存，数据库只读
• 时间限制：12小时
• 最小平均召回率：0.8
• 数据集：GOOAQ（300 万个384维向量）
• 目标：通过数据集构建K-NN近邻图
  • 通过与提供的golden standard（标准K-NN近邻图）进行比较（计算召回率），模型间也会比较时间损耗（包括预处理、索引、搜索和后处理）
  • 提供开发数据集；评估阶段将使用相同神经模型计算的类似大小的未公开数据集

参与、注册

• 在 GitHub 仓库 注册。
• 提交的解决方案需通过 Docker 容器运行，并提供操作指南

重要日期

• 提交解决方案截止日期：6月6日

• 短论文提交截止日期：6月13日

• 排名公告：7月1日

24 VS 25

这里调研了24年的挑战，汲取一下前届参赛者的经验

挑战任务简介

• 任务 1：不受限制的索引构建，12小时构建时间，目标是实现最高的搜索性能

• 任务 2：内存受限的索引构建（带重新排序），8核32GB RAM，24小时构建时间，要求在有限的内存和存储资源下优化性能

• 任务 3：内存受限的索引构建（无重新排序），不限CPU核数64GB RAM，12小时构建时间，强调在更高内存容量下直接优化索引性能

25的索引挑战要求带重新排序，8核36GB RAM，12小时构建时间，更严格。

区别

24年挑战总览

完成挑战的一共有五个项目（算上官方提供的baseline）：BL-SearchGraph, DEGLIB, HSP, HIOB, LMI
以下效果都是私有查询集下的结果（out-of-distribution），也就是说在提供的查询集下达到标准并不意味着在别的查询集依然可以完成挑战。

2024	任务1	任务2	任务3
效果
评价	DEGLIB 和 LMI 团队超过了任务指定的0.8且DEGLIB取得最佳	LMI超时，BL-SearchGraph和HIOB均未达到0.8的要求	DEGLIB、HIOB 和 LMI达到要求，DEGLIB更快，LMI更准

总结

• DEGLIB基于crEG（论文中为了加速增添限制使得丢失动态特性，成为静态构图，构建出类似MRNG近邻图，BS搜索）结合MLP压缩特征向量，有涉及到选点来加速，可以看出在内存限制不太严的时候，速度是很快的，限制内存会影响该模型的召回率，所以可提升的方向在于空间利用率
• BL-SearchGraph基于NSW增量式构建方法（动态构图，构建出类似KNN近邻图，BS搜索），搜索时在原有基础上引入了一个超参数Δ和动态K机制来调整模型效果
• HSP是一种HNSW的版本（构建出类似MRNG近邻图，有局部单调性，BS搜索），采用逻辑多层结构来构建但是物理上并没有分层，准确率上可能好于HNSW，但是在构建时间和速度上不及HNSW
• LMI采用ML方式学出来索引，优点是查询效率随召回率升高下降少且如果可以构建出来应该可以满足召回率要求，缺点是查询效率较低以及可能构建时间较长
• HIOB采用Sketching Techniques（摘要技术），利用映射后的二进制表示并对其分组来约减，采用汉明距离

杂记

前面三种方法都是基于近邻图的方法：

• 采用邻居图来构建索引，其中节点代表数据点，边表示相似数据点间的连接。
• 使用贪心搜索进行查询，从某个点出发，沿着最接近查询点的边移动。
• 通过优化图结构（如削减冗余边）提高搜索速度和准确性。

与传统方法对比

• 局部敏感哈希（LSH）：基于哈希函数将相似数据映射到相同桶中，加速搜索，但受限于高维数据的稀疏性。
• 产品量化（Product Quantization, PQ）：对数据进行量化以减少存储和计算开销，如SCANN优化了PQ的损失函数以提升搜索质量。
• 层次化导航小世界图（HNSW）：构建多层次索引，提高搜索效率，但索引构建成本较高。
• 素描技术（Sketching techniques）：在计算机科学中指的是利用数据摘要（sketch）来进行高效计算，将高维数据转换成紧凑的低维表示，在保持数据重要特性的同时减少计算和存储成本。既不同于 LSH 也不同于 PQ，但与 LSH 关系更近。它是一种更广义的近似计算方法，既可以用于近似最近邻搜索，也可以用于流数据处理、统计计算等场景。