mlsanityData to 7 Oct 2026

PDX: A Data Layout for Vector Similarity Search

arXiv 2503.04422 ↗First posted 6 Mar 2025cs.DB cs.AIcited by 8

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 20 of its 57 references that are in the map. First posted on arXiv 6 Mar 2025.

Builds on

20 of 57 references.

References · 20

  1. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
  2. 2018ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithmscited by 130
  3. 2016A Survey on Learning to Hashcited by 119
  4. 2017Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphcited by 103
  5. 2021A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Searchcited by 82
  6. 2024RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Searchcited by 46
  7. 2021A Survey on Locality Sensitive Hashing Algorithms and their Applicationscited by 40
  8. 2023High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operationscited by 25
  9. 2018Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Datacited by 20
  10. 2023Similarity search in the blink of an eye with compressed indicescited by 20
  11. 2024Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segmentcited by 16
  12. 2024BANG: Billion-Scale Approximate Nearest Neighbor Search using a Single GPUcited by 14
8 more
  1. 2024Locally-Adaptive Quantization for Streaming Vector Searchcited by 10
  2. 2016Polysemous codescited by 8
  3. 2024Effective and General Distance Computation for Approximate Nearest Neighbor Searchcited by 8
  4. 2021Low-Precision Quantization for Efficient Nearest Neighbor Searchcited by 6
  5. 2018uops.info: Characterizing Latency, Throughput, and Port Usage of Instructions on Intel Microarchitecturescited by 5
  6. 2024AiSAQ: All-in-Storage ANNS with Product Quantization for DRAM-free Information Retrievalcited by 5
  7. 2024CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestioncited by 4
  8. 2024Efficient Data Access Paths for Mixed Vector-Relational Searchcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 5.

8 papers.

  1. 2025Panorama: Fast-Track Nearest Neighborscited by 2
  2. 2026A Super Fast K-means for Indexing Vector Embeddingscited by 2
  3. 2025Bang for the Buck: Vector Search on Cloud CPUscited by 1
  4. 2025Exqutor: Extended Query Optimizer for Vector-augmented Analytical Queriescited by 0
  5. 2026CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Datacited by 0
  6. 2026Semantic Recall for Vector Searchcited by 0
  7. 2026ANN Search: Recall What Matterscited by 0
  8. 2026Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddingscited by 0