ETD

• anns
• Darth
• hnsw
• neighbor
• query
• termination
• vector

This thesis analyzes DARTH, a learned early-termination method for Approximate Nearest Neighbor Search, with a specific focus on HNSW. The work starts from a limitation of static search control through efSearch: the same search budget is applied to all queries, even though different queries may need different amounts of graph exploration to reach the same recall.

The thesis reproduces the original DARTH pipeline, integrates the method into Kannolo, an independent Rust-based HNSW framework, and evaluates the recall predictor inside the query loop through QuickScorer-rs. The results are then reassessed with a recall-matched protocol, comparing DARTH against the fastest plain HNSW configuration that reaches at least the same mean recall.

The results show that DARTH works as an early-termination mechanism over a conservative high-budget HNSW trajectory. However, when the comparison is made against calibrated static HNSW, many apparent speedups shrink to parity or disappear. The conclusion is that DARTH is not superior to calibrated HNSW.

Questa tesi analizza DARTH, un metodo di early termination per la ricerca approssimata dei vicini più prossimi, con particolare attenzione a HNSW. Il lavoro parte dal limite del controllo statico tramite efSearch: lo stesso budget di ricerca viene applicato a tutte le query, anche se query diverse possono richiedere quantità diverse di esplorazione per raggiungere la stessa recall.

La tesi riproduce la pipeline originale di DARTH, integra il metodo in Kannolo, un framework HNSW indipendente scritto in Rust, e valuta il predittore tramite QuickScorer-rs durante il ciclo di query. Infine, i risultati vengono rivalutati con un protocollo recall-matched, confrontando DARTH con la configurazione plain HNSW più veloce che raggiunge almeno la stessa recall media.

I risultati mostrano che DARTH funziona come meccanismo di interruzione anticipata rispetto a una ricerca HNSW conservativa ad alto budget. Tuttavia, quando il confronto viene fatto contro HNSW statico calibrato, molti speedup si riducono fino alla parità o scompaiono. La conclusione è che DARTH non è superiore a HNSW calibrato.