MemANNS: Enhancing Billion-Scale ANNS Efficiency with Practical PIM Hardware
Authors:
Preprint
Abstract
In numerous production environments, Approximate Nearest Neighbor Search (ANNS) plays an indispensable role, particularly when dealing with massive datasets that can contain billions of entries. The necessity for rapid response times in these applications makes the efficiency of ANNS algorithms crucial. However, traditional ANNS approaches encounter substantial challenges at the billion-scale level. CPU-based methods are hindered by the limitations of memory bandwidth, while GPU-based methods struggle with memory capacity and resource utilization efficiency. This paper introduces MemANNS, an innovative framework that utilizes UPMEM PIM architecture to address the memory bottlenecks in ANNS algorithms at scale. We concentrate on optimizing a well-known ANNS algorithm, IVFPQ, for PIM hardware through several techniques. First, we introduce an architecture-aware strategy for data placement and query scheduling that ensures an even distribution of workload across PIM chips, thereby maximizing the use of aggregated memory bandwidth. Additionally, we have developed an efficient thread scheduling mechanism that capitalizes on PIM's multi-threading capabilities and enhances memory management to boost cache efficiency. Moreover, we have recognized that real-world datasets often feature vectors with frequently co-occurring items. To address this, we propose a novel encoding method for IVFPQ that minimizes memory accesses during query processing. Our comprehensive evaluation using actual PIM hardware and real-world datasets at the billion-scale, show that MemANNS offers a significant 4.3x increase in QPS over CPU-based Faiss, and it matches the performance of GPU-based Faiss implementations. Additionally, MemANNS improves energy efficiency, with a 2.3x enhancement in QPS/Watt compared to GPU solutions.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Proxima: Near-Storage Acceleration for Graph-Based Approximate Nearest Neighbor Search in 3D NANDIEEE Transactions on Computers, 2026
- BANG: Billion-Scale Approximate Nearest Neighbour Search Using a Single GPUIEEE Transactions on Big Data, 2025
- SwiftRL: Towards Efficient Reinforcement Learning on Real Processing-In-Memory Systems2024
- NDRec: A Near-Data Processing System for Training Large-Scale Recommendation ModelsIEEE Transactions on Computers, 2024
- High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison OperationsProceedings of the ACM on Management of Data, 2023
- Benchmarking a New Paradigm: Experimental Analysis and Characterization of a Real Processing-in-Memory SystemIEEE Access, 2022
- GGNN: Graph-Based GPU Nearest Neighbor SearchIEEE Transactions on Big Data, 2022
- Accelerating Large-Scale Graph-Based Nearest Neighbor Search on a Computational Storage PlatformIEEE Transactions on Computers, 2022
- Billion-Scale Similarity Search with GPUsIEEE Transactions on Big Data, 2019
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010