https://github.com/swar09/photon
How I reached this approach?
In the beginning, I was going with a normal graph data structure and BFS/DFS. Brute-force algorithms created an adjacency matrix. Then I realized this is not for large data, so I moved to an adjacency list implemented using the following struct:
// here T is any type
// at this stage T = f32
pub struct AdjList<T> {
connections: Vec<Vec<T>>;
}
This is very expensive to store floating points in Vec<Vec<f32>>. Very high latency because Vec<> is a contiguous data type that stores sequentially in the heap, but Vec<Vec<>> is like steps, it is scattered. Latency increases because we jump from one memory address to another. I was using pub fn brute_force_search() to check each and every vector and calculate Euclidean distance or cosine similarity. $O(N)$ time complexity, we can't use this for large datasets. It's a very inefficient algorithm.
If we use this data structure, we will keep jumping from one memory address to another, which is expensive and time-consuming.
Then I implemented pub fn greedy_search(). This comes with a tradeoff! Slightly accuracy drop (1% to 5% maybe) but time complexity of $O(\log N)$ Much better! This reduced the search time drastically, but still, vector search is slow due to the adjacency list approach. I was storing f32 in Vec<Vec<f32>>still very inefficient.
Then I got to know about HNSW (Hierarchical Navigable Small World graphs), which is a very efficient algorithm with minimal accuracy tradeoff. Implemented this using HashMaps only, but within minutes before query search, I realized this is way too complex and not efficient!
In the HNSW algorithm, we basically create layers of graphs which are interconnected (not actually, but assume). We start the search from the top layer from an entry node. We have a set of [closest neighbors]; here we use a greedy algorithm and return the closest neighbors (its corresponding vector). Here they are not actually connected, but they are promoted. Layer 0 has $N$ nodes, then some $M$ nodes will be promoted to Layer 1, and this will continue until $n$ layers are formed. On Layer $n$, we have the entry point.
First, we get $Euclidean\ distance(Qv, Ev)$ where $\{Q \to \text{Search query vector}, E \to \text{entry point node’s vector}\}$. Then we create a list which will store, let's say, $m$ closest neighbors, then another list where we store the visited nodes. Then we take the distance between $Q$ and neighbors of $EP$ in Layer $n-1$, then we go down by doing this same process again and again. When we reach Layer 0, we get our closest neighbors from the list.
Now, how do we create these layers? Which node gets promoted? All is decided by a random function, and the layer count is decided by an $exponential\ decay\ probability\ function$.
pub struct VectorStore {
pub data: Vec<f32>,
pub dim: usize,
}
pub struct GraphLayers {
pub base_layer: Vec<Vec<usize>>,
pub upper_layers: Vec<HashMap<usize, Vec<usize>>>,
}
pub struct HNSW {
pub layers: GraphLayers,
pub vectors: VectorStore,
pub entry_point: Option<usize>,
pub max_level: usize,
pub ef_construction: usize,
pub m: usize,
}
Why this randomness works:
If we just picked nodes manually, we’d end up with "hubs" that bottleneck the search. By using the exponential decay function, we ensure the top layers stay sparse giving us those "long-range" jumps across the data space—while the bottom layers stay dense for fine-grained accuracy. It’s like a skip-list but for high-dimensional space; it prevents the search from getting stuck in local minimums by forcing it to look at the "big picture" first before diving into the weeds. Without this probabilistic layering, you're just doing a greedy search on a flat graph, which is a one-way ticket to high latency and terrible recall.
