Framework for multi-objective optimization with partially specified preferences in a distributed setting

On a daily basis, people need to make decisions with conflicting objectives in mind. For instance, deciding which flight to book or which accommodation to rent for the summer vacation. In this case, there is a clash between the objectives we want to maximize. Related to the previous example, suppose we want to find a good quality apartment with a small distance from the beach and a low price. Although efficient algorithms exist that tackle this problem, they require a high level of precision from the user, which is often not available. Indeed, users are typically expected to specify their preferences by defining exact weights for each objective, which is not convenient. Motivated by this, in this thesis we introduce the novel Flexible Score Aggregation (FSA) approach, which offers a user-centric design that lets users specify their preferences by imposing constraints. That is to say, the user doesn't need to indicate any weights with absolute accuracy. We leverage on skyline queries and top-k queries as classical approaches, as well as their integration (known under the name of R- Skylines). We propose a generalization of these approaches in order to rapidly retrieve the best objects from a database in a distributed environment. We show that the FSA approach has a particular form of optimality called instance optimality. Moreover, the proposed approach can easily find its implementation in modern data-intensive applications that collect data from distributed sites as we demonstrate through two use cases. Finally, we show this approach to be effective and efficient by performing extensive experiments on real and synthetic datasets.

Ogni giorno le persone si ritrovano a effettuare delle scelte con obiettivi contrastanti tra loro, ad esempio, nel decidere quale volo o hotel prenotare per le vacanze estive. In questo caso, ci sono obiettivi discordanti da raggiungere. Riprendendo l’esempio citato, si supponga infatti di voler scegliere un buon appartamento, che si trovi vicino alla spiaggia e che abbia un prezzo conveniente. Anche se esistono algoritmi efficienti per affrontare il problema, essi richiedono una notevole precisione da parte dell’utente, spesso non disponibile. Gli utenti dovrebbero, infatti, saper definire le proprie preferenze attribuendo uno specifico peso ad ogni obiettivo. Partendo da questo presupposto, con il presente lavoro di tesi si vuole introdurre il nuovo approccio Flexible Score Aggregation (FSA), che offre una soluzione incentrata sull’utente che gli permetta di esplicitare le proprie preferenze attraverso l’imposizione di vincoli. In questo modo l’utente non è tenuto a indicare pesi specifici con assoluta accuratezza. Saranno utilizzate query skyline e query top-k come approcci classici, così come loro combinazioni (conosciute come R-skyline). Sarà proposta una generalizzazione dei suddetti approcci al fine di reperire velocemente le migliori soluzioni in un database distribuito. Sarà dimostrato che l’approccio FSA può convergere in una soluzione che gode di un tipo di ottimalità detta instance optimality. Sarà inoltre dimostrato, attraverso due casi d’uso, come l’approccio proposto possa essere facilmente implementato nelle moderne applicazioni data-intensive che raccolgono dati da sistemi distribuiti. Infine, attraverso test di performance condotti su dataset reali e su dataset ad hoc, sarà dimostrato come l’approccio sia efficace ed efficiente.