MS thesis, NYU Tandon School of Engineering, 2026. Advised by Prof. Torsten Suel.
Thesis PDF · Defense slides · C++ implementation · Interactive demo
Graph-based ANN indexes (Vamana, HNSW, NSG) answer queries by greedy traversal: start at an entry point, move to whichever neighbor is closest to the query, stop at a local minimum. Navigability asks whether that traversal can actually reach a given target. The monotone RNG guarantees this from every node, but is far too expensive to build on real datasets — and the guarantee is stronger than necessary, since practical indexes always search from one fixed entry point.
So the thesis asks: what do you gain by guaranteeing navigability only from the designated entry point?
- a formalization of single-source navigability for directed proximity graphs
- construction algorithms that enforce it by augmenting a baseline graph with extra edges
- analysis of the augmented structure, and optimizations that close the gap between the theoretical construction and practical performance
- experiments on SIFT-small: the final algorithm beats state-of-the-art Vamana construction on the computation-recall tradeoff in some parameter regimes, for both in-graph and out-of-sample queries
Needs a TeX distribution with pdflatex and bibtex.
make # thesis -> main.pdf
make slides # defense slides -> slides.pdf