Please note: This master’s thesis presentation will take place in DC 3301 (DSG Lab).
Arman Davoodi, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Tamer Özsu
Approximate Nearest Neighbour Search (ANNS) is widely used to search large, high-dimensional vector datasets, but deploying vector indices on memory-disaggregated platforms introduces additional challenges because index data must be accessed through a remote-memory interconnect. Existing memory-disaggregated ANNS implementations primarily focus on graph-based indices or rely on specialized hardware and near-memory computation. This thesis investigates an alternative approach based on inverted file (IVF) indices, whose cluster-based organization provides structured data locality that can be exploited for remote transfers and compute-node caching.
We present DIVF, an IVF-based framework for ANNS on RDMA-based memory-disaggregated platforms with multiple Compute Nodes (CNs) and a passive Memory Node (MN). The framework separates query execution, CN-side memory management, and RDMA communication into an Index Layer, Buffer Manager, and RDMA Engine. We first develop DIVF-Flat, a disaggregated implementation of conventional flat IVF. We then introduce Capped DIVF-Flat, which uses capacity-constrained clustering to bound cluster sizes and simplify remote-memory transfer and cache management. Finally, we propose DIVF-Tree, a hierarchical IVF structure that recursively indexes cluster centroids to reduce the routing overhead of flat IVF while retaining bounded cluster sizes. The implementation supports asynchronous task-based query processing, CN-side cluster caching, and one-sided RDMA Reads without requiring memory-side query computation.
We evaluate the proposed designs using the BIGANN benchmark on a real RDMA-based memory-disaggregated platform, including experiments on the full dataset containing approximately one billion unique vectors. The evaluation characterizes the effects of index-construction and search parameters, dataset scale, CN cache capacity, worker-thread count, and the number of CNs. On the billion-vector dataset, DIVF-Tree achieves approximately 6.2x higher throughput than DIVF-Flat at a comparable Recall@10 of approximately 0.74, while outperforming both evaluated flat IVF variants throughout their overlapping recall range. The results also show that additional CN cache capacity can substantially improve throughput by reducing remote leaf-cluster accesses, and that DIVF-Tree exhibits substantially less than proportional throughput degradation as the evaluated dataset size increases.
Finally, the scalability experiments show that increasing compute resources alone provides limited benefit once the shared remote-access path appears to become throughput-limiting. In contrast, higher cache capacity and query reuse substantially improve both thread and CN scaling. These results indicate that efficient memory-disaggregated ANNS depends not only on reducing the amount of remotely transferred data, but also on improving cache locality and reducing the frequency with which queries require remote-memory access.