Locality Sensitive Hashing basato sull'entropia per la ricerca approssimata del vicino più prossimo

This thesis investigates approximate nearest neighbor search in high-dimensional spaces through Locality-Sensitive Hashing (LSH), with particular focus on the entropy-based approach proposed by Panigrahy. After analyzing the theoretical foundations of entropy-guided search, including its probabilistic guarantees and complexity analysis, we study the limitations of relying on a fixed analytical estimate of the bucket entropy. Building upon this analysis, we explore an adaptive search strategy in which the entropy of the bucket distribution is estimated online during query execution. This enables a dynamic stopping rule that aims to preserve probabilistic guarantees while adapting the computational effort to the structure of the data.

La presente tesi analizza il problema della ricerca approssimata del vicino più prossimo in spazi ad alta dimensionalità mediante tecniche di Locality-Sensitive Hashing (LSH), con particolare attenzione all'approccio basato sull'entropia proposto da Panigrahy. Dopo aver studiato i fondamenti teorici del metodo, le sue garanzie probabilistiche e la relativa analisi di complessità, ci siamo concentrati sui limiti derivanti dall'utilizzo di una stima analitica e fissa dell'entropia della distribuzione dei bucket. Sulla base di tali considerazioni, abbiamo esplorato una strategia di ricerca adattiva nella quale l'entropia viene stimata dinamicamente durante l'esecuzione della query. Ciò permette di definire una regola di arresto che mantenga le garanzie probabilistiche adattando al contempo il costo computazionale alla struttura dei dati.