PDX: A Data Layout for Vector Similarity Search
作者: Leonardo Kuffo, Elena Krippner, Peter Boncz
发布时间: 2025-03-07
来源: arxiv
研究方向: 向量相似度搜索（Vector Similarity Search）
主要内容
提出了PDX数据布局，该布局旨在优化向量相似度搜索的性能，特别是通过改进现有维度剪枝算法（如ADSampling和BSA）的效率。
主要贡献
1. 设计并实现了PDX数据布局，该布局能够提高向量相似度搜索的效率。
2. 开发了一个名为PDXearch的搜索框架，该框架利用PDX布局进行高效的维度剪枝搜索。
3. 提出了PDX-BOND算法，该算法利用PDX布局进行精确搜索，同时避免了剪枝算法的召回率损失。
4. 提供了一个开源的C++实现，以及Python绑定，以方便使用。
5. 在多个数据集和CPU架构上进行了实验，证明了PDX在精确和近似搜索中的优势。
研究方法
1. 数据布局设计：PDX布局将维度分组存储，允许更高效的维度剪枝搜索。
2. 搜索框架：PDXearch框架通过自适应地扫描维度来提高搜索效率。
3. 算法优化：PDX-BOND算法通过优先访问与查询最相关的维度来提高搜索性能。
4. 实验评估：在多个数据集和CPU架构上进行了实验，以验证PDX的有效性。
实验结果
实验结果表明，PDX在精确和近似搜索中均优于现有的方法，尤其是在高维数据集上。PDX-BOND算法在精确搜索中表现出色，并且不需要预处理数据。
未来工作
未来工作可能包括将PDX布局扩展到图形索引，优化PDX在内存受限环境中的性能，以及探索将PDX与其他数据压缩和量化技术相结合的方法。