PDX通过分维存储加速向量相似性搜索，无需复杂优化即可提速40%以上。
PDX: A Data Layout for Vector Similarity Search
- 将向量按维度垂直分块存储，支持多向量并行处理
- 相比传统布局快40%，结合剪枝算法可提速2-7倍
- 无需预处理即可直接使用，适合频繁更新的向量数据库
我们提出PDX，一种面向向量（如嵌入）的数据布局，类似PAX [6]，将多个向量存于同一块中，采用垂直维度布局（图1）。得益于逐维度搜索策略，能以紧致循环同时处理多个向量，显著加速精确与近似相似性搜索。PDX在标准水平向量存储上比SIMD优化的距离核平均快40%，仅依赖可自动向量化的基本标量代码。我们将PDX与近期维度剪枝算法ADSampling [19] 和 BSA [52] 结合，发现这些算法在水平布局下可能因被SIMD优化的线性扫描超越而失效；但在PDX上恢复性能优势，提升2-7倍。我们发现当仅需全扫描有限维度时，PDX搜索尤其快速——这正是维度剪枝方法的特征。最后引入PDX-BOND，一种更灵活的剪枝策略，在精确搜索中表现优异，近似搜索亦具合理性能。与以往方法不同，它可直接作用于原始向量数据，无需预处理，适用于频繁更新的向量数据库。
原文摘要 · Abstract (English)
We propose Partition Dimensions Across (PDX), a data layout for vectors (e.g., embeddings) that, similar to PAX [6], stores multiple vectors in one block, using a vertical layout for the dimensions (Figure 1). PDX accelerates exact and approximate similarity search thanks to its dimension-by-dimension search strategy that operates on multiple-vectors-at-a-time in tight loops. It beats SIMD-optimized distance kernels on standard horizontal vector storage (avg 40% faster), only relying on scalar code that gets auto-vectorized. We combined the PDX layout with recent dimension-pruning algorithms ADSampling [19] and BSA [52] that accelerate approximate vector search. We found that these algorithms on the horizontal vector layout can lose to SIMD-optimized linear scans, even if they are SIMD-optimized. However, when used on PDX, their benefit is restored to 2-7x. We find that search on PDX is especially fast if a limited number of dimensions has to be scanned fully, which is what the dimension-pruning approaches do. We finally introduce PDX-BOND, an even more flexible dimension-pruning strategy, with good performance on exact search and reasonable performance on approximate search. Unlike previous pruning algorithms, it can work on vector data "as-is" without preprocessing; making it attractive for vector databases with frequent updates.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。