Result diversification. Space partitioning & probing : batched access

Negli ultimi anni le ricerche sul web hanno avuto un impatto sempre maggiore nella vita delle persone. In particolare motori di ricerca su argomenti specifici, come hotel, compagnie aeree, case in vendita e molti altri, sono sempre più utilizzati ed apprezzati. Per molte di queste ricerche, però, non sono sufficienti algoritmi semplici, infatti, molto spesso, le esigenze degli utenti sono molto varie e sfaccettate. Pensiamo un attimo a ricerche composte su più domini diversi, ad esempio una ricerca combinata di aerei e case vacanze. Per poter soddisfare ricerche di questo tipo servono algoritmi che estraggano risultati da più data service e li combinino secondo determinate funzioni, per ottenere dei dati rilevanti per l'utente finale. Uno di questi casi particolari, è il problema della diversificazione dei risultati, ossia l'esigenza da parte dell'utente di ottenere dei risultati che non siano ordinati secondo un solo parametro (ad esempio il prezzo), ma che siano fra loro il più vario possibile; quindi ad esempio una ricerca sugli hotel non dovrebbe fornire solo i risultati in ordine di prezzo, ma mostrare l'hotel più costoso, il più economico, quello con una valutazione dei clienti migliore e magari quello più vicino ad un luogo particolare. Alcuni algoritmi di diversificazione dei risultati sono stati proposti in letteratura, fra questi MMR è il più conosciuto ed usato. Il punto di partenza di questo lavoro di tesi è SPP un algoritmo di diversificazione spaziale basato su strutture geometriche. L'obiettivo di SPP era di ottenere gli stessi risultati di MMR accedendo ad un numero molto minore di oggetti, per migliorare le prestazioni del sistema. Il mio scopo, con questo lavoro, è stato quello di studiare la politica di accesso agli oggetti di SPP per trovare dei possibili miglioramenti. Mi sono focalizzato in particolare su una versione dell'algoritmo che accede, ad ogni iterazione, ad un numero di oggetti determinato da un budget, studiando in che modo far variare questo budget per ottenere risultati migliori.