# PDX: A Data Layout for Vector Similarity Search

arXiv: https://arxiv.org/abs/2503.04422 · HTML: https://mlsanity.com/paper/2503.04422/

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [A Survey on Learning to Hash](https://mlsanity.com/paper/1606.00185/) (2016)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2405.12497/) (2024)
- [A Survey on Locality Sensitive Hashing Algorithms and their Applications](https://mlsanity.com/paper/2102.08942/) (2021)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [Similarity search in the blink of an eye with compressed indices](https://mlsanity.com/paper/2304.04759/) (2023)
- [Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data](https://mlsanity.com/paper/1810.07355/) (2018)
- [Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment](https://mlsanity.com/paper/2401.02116/) (2024)
- [BANG: Billion-Scale Approximate Nearest Neighbor Search using a Single GPU](https://mlsanity.com/paper/2401.11324/) (2024)
- [Locally-Adaptive Quantization for Streaming Vector Search](https://mlsanity.com/paper/2402.02044/) (2024)
- [Polysemous codes](https://mlsanity.com/paper/1609.01882/) (2016)
- [Effective and General Distance Computation for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2404.16322/) (2024)
- [Low-Precision Quantization for Efficient Nearest Neighbor Search](https://mlsanity.com/paper/2110.08919/) (2021)
- [uops.info: Characterizing Latency, Throughput, and Port Usage of Instructions on Intel Microarchitectures](https://mlsanity.com/paper/1810.04610/) (2018)
- [AiSAQ: All-in-Storage ANNS with Product Quantization for DRAM-free Information Retrieval](https://mlsanity.com/paper/2404.06004/) (2024)
- [CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion](https://mlsanity.com/paper/2406.19651/) (2024)
- [Efficient Data Access Paths for Mixed Vector-Relational Search](https://mlsanity.com/paper/2403.15807/) (2024)

## Built on by (most cited first, 8 of 8)

- [Panorama: Fast-Track Nearest Neighbors](https://mlsanity.com/paper/2510.00566/) (2025)
- [A Super Fast K-means for Indexing Vector Embeddings](https://mlsanity.com/paper/2603.20009/) (2026)
- [Bang for the Buck: Vector Search on Cloud CPUs](https://mlsanity.com/paper/2505.07621/) (2025)
- [Exqutor: Extended Query Optimizer for Vector-augmented Analytical Queries](https://mlsanity.com/paper/2512.09695/) (2025)
- [CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data](https://mlsanity.com/paper/2604.06616/) (2026)
- [Semantic Recall for Vector Search](https://mlsanity.com/paper/2604.20417/) (2026)
- [ANN Search: Recall What Matters](https://mlsanity.com/paper/2606.04522/) (2026)
- [Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings](https://mlsanity.com/paper/2608.14648/) (2026)

## 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.