Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
Authors: Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, Torsten Suel
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | First, we give a simple and efficient way to construct a navigable graph with average degree O( n log n) for any set of n points, in any dimension, for any distance function. We compliment this result with a nearly matching lower bound: even under the Euclidean metric in O(log n) dimensions, a random point set has no navigable graph with average degree O(nα) for any α < 1/2. The main contribution of this work is to provide tight upper and lower bounds on the sparsity required to construct navigable graphs for high-dimensional point sets. |
| Researcher Affiliation | Academia | Haya Diwan New York University hd2371@nyu.edu; Jinrui Gou New York University jg6226@nyu.edu; Cameron Musco UMass Amherst cmusco@cs.umass.edu; Christopher Musco New York University cmusco@nyu.edu; Torsten Suel New York University torsten.suel@nyu.edu |
| Pseudocode | Yes | Algorithm 1 Greedy Search |
| Open Source Code | No | The paper does not provide any explicit statements or links to open-source code for the described methodology. The NeurIPS checklist indicates no experiments and thus no code release. |
| Open Datasets | No | The paper is theoretical and does not mention using any public or open datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental validation or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, hyperparameters, or system-level training settings. |