In what ways do tree-based indices (such as Annoy’s random projection forests) differ from graph-based indices (like HNSW) in terms of search speed and recall?

Tree-based indices (like Annoy’s random projection forests) and graph-based indices (such as HNSW) differ in how they organize data and perform searches, leading to distinct trade-offs in speed and recall. Tree-based methods partition data hierarchically using decision boundaries (e.g., random hyperplanes), while graph-based approaches model relationships between data points as interconnected nodes. These structural differences directly impact their performance characteristics.

In terms of search speed, tree-based indices often have predictable latency because they traverse fixed hierarchical structures. For example, Annoy builds multiple binary trees, and each search involves descending each tree to a leaf node and aggregating results. However, the need to query multiple trees (to improve recall) can increase computational overhead. Graph-based methods like HNSW, by contrast, use a hierarchy of graphs where searches start at coarse layers and refine results in finer layers. This “zoom-in” approach allows HNSW to skip irrelevant regions quickly, often leading to faster search times—especially in high-dimensional spaces. For instance, HNSW might require fewer distance computations than Annoy for the same recall, as graph edges directly encode proximity relationships.

Recall differences stem from how well each method handles the “curse of dimensionality.” Tree-based indices rely on partitioning, which can struggle with high-dimensional data because hyperplanes may split natural clusters, leading to missed neighbors. Annoy mitigates this by using multiple trees (reducing variance), but increasing the tree count trades off with slower searches. HNSW, on the other hand, maintains recall more effectively in high dimensions because its graph layers preserve local and long-range connections. For example, HNSW’s “small world” property ensures that any node is reachable in a small number of steps, reducing the risk of overlooking true nearest neighbors. In benchmarks, HNSW often achieves higher recall at similar speed levels compared to Annoy, especially when datasets are large or dimensions exceed 100.

Practical considerations further highlight these differences. Annoy is simpler to implement and requires less memory, making it suitable for scenarios where index construction time or resource constraints matter. For example, a developer with a medium-sized dataset (e.g., 1M embeddings in 50D) might prefer Annoy for its balance of speed and simplicity. HNSW, while more complex to tune (e.g., managing layer counts and edge connections), excels in high-performance applications like large-scale recommendation systems, where sub-millisecond latency and >95% recall are critical. The choice ultimately depends on the problem’s dimensionality, dataset size, and tolerance for trade-offs between speed and accuracy.