GitHub user i18n-now added a comment to the discussion: [Proposal] Vector Similarity Search Indexing
DiskANN++：使用查询敏感度入口顶点对同构映射图索引进行高效的基于页面的搜索 https://www.semanticscholar.org/paper/DiskANN%2B%2B%3A-Efficient-Page-based-Search-over-Mapped-Ni-Xu/dadc18320a7dea60ec8fe6dfd3595943c78952e2 给定一个向量数据集 $\mathcal{X}$ 和一个查询向量 $\vec{x}_q$，基于图的近似最近邻搜索 (ANNS) 旨在构建一个图索引 $G$，并通过搜索 $G$ 近似返回与 $\vec{x}_q$ 距离最小的向量。基于图的 ANNS 的主要缺点是图索引太大，无法放入内存，尤其是对于大规模的 $\mathcal{X}$。为了解决这个问题，提出了一种基于乘积量化 (PQ) 的混合方法 DiskANN，将低维 PQ 索引存储在内存中，并将图索引保留在 SSD 中，从而在确保高搜索精度的同时减少内存开销。然而，它存在两个 I/O 问题，会严重影响整体效率：(1) 从入口顶点到查询邻域的长路由路径导致大量 I/O 请求和 (2) 路由过程中的冗余 I/O 请求。我们提出了一个优化的 DiskANN++ 来克服上述问题。具体来说，对于第一个问题，我们提出了一种查询敏感的入口顶点选择策略，用动态确定的接近查询的入口顶点替换 DiskANN 的静态� �中心入口顶点。对于第二个 I/O 问题，我们提出了一种基于 DiskANN 图索引的同构映射来优化 SSD 布局，并提出了一种基于优化的 SSD 布局的异步优化页面搜索作为 DiskANN 束搜索的替代方案。对八个真实数据集的全面实验研究表明我们的 DiskANN++ 在效率方面具有优势。在相同的准确度约束下，与 DiskANN 相比，我们的 QPS 显著提高了 1.5 倍到 2.2 倍。 GitHub link: https://github.com/apache/kvrocks/discussions/2287#discussioncomment-9657192 ---- This is an automatically sent email for [email protected]. To unsubscribe, please send an email to: [email protected]
