Graph-based indexes support state of the art approximate nearest-neighbor search throughput at high recall but take hours or days to build on the large datasets characteristic of modern workloads. This is caused by their reliance on queries over the partial index during construction. This dissertation argues that graph-index and k-NN graph construction should instead leverage a partitioning-based approach which cuts build time by an order of magnitude at equal quality on CPUs, on GPUs, and, as proposed here, in dynamic and distributed settings.

We recently introduced PiPNN (KDD 2026), which recursively partitions the data into small overlapping clusters, computes all pairwise distances within each, and prunes the candidates with HashPrune, an online, history-independent rule. It builds up to 11.6x faster than Vamana (DiskANN) and 12.9x faster than HNSW, and indexes a billion points in under 20 minutes on one machine. Our followup works, PiPNN II and GPIPNN (under submission), use quantized, fused matrix-multiply/top-k kernels. They build up to 8x faster than PiPNN on CPUs and 40.7x faster (geometric mean) than unquantized Vamana. On an H100 GPU, GPiPNN produces proximity graphs to 43.7x faster than the state of the art Jasper method and 50x faster than CAGRA at matching query throughput. It produces k-NN graphs up to 13x (CPU) and 6.6x (GPU) faster than the best prior methods. A quantized PiPNN variant with a 1-bit Hamming pre-filter and NN-descent refinement won Task~1 (k-NN graph construction) of the SISAP 2026 Indexing Challenge.

Dynamic PiPNN will apply streaming insertions and deletions as partition-local batches, relying on the history-independence of HashPrune. We will compare its recall stability and update throughput with FreshDiskANN-style in-place updates. Distributed PiPNN will index tens of billions of vectors on a multi-GPU node and then a cluster, with associative HashPrune merges and no coordination.