Member-only story
An Intuition of Graph Based Indexing
In Graph-based indexing, we represent data points as nodes within a graph, where the edges between these nodes stand for the similarity or distance between data points.
This method stands in contrast to traditional indexing methods, which often struggle with the “curse of dimensionality,” wherein the performance of algorithms deteriorates as the dimensionality of the data increases.
One of the most notable techniques in graph-based indexing is the Hierarchical Navigable Small World (HNSW) graph.
The HNSW graph leverages the small-world phenomenon (see note at the end of this article), where most nodes can be reached from every other by a small number of steps, to enhance the efficiency of indexing and retrieving high-dimensional data.
This is achieved by organizing the graph into multiple layers, with each layer representing a different granularity of the dataset. The top layers contain fewer nodes, which represent…
