Measuring and enhancing linear top-k queries' ability to discover the skyline

Linear top-k queries are the most commonly implemented type of ranking query, being fast to execute and able to suit the user's needs. Despite its advantages, this approach to multi-objective optimization isn't always optimal, often failing to highlight some relevant records present inside the collection that is being searched. These records can instead be identified by skyline queries, which are optimal but also slow and unpractical. In this thesis, the ability of linear top-k queries of discovering optimal solutions will be analyzed, first using appropriate metrics and indicators on real data and then through a more rigorous, theoretical methodology. Later on, an original query, the Var-k query, will be proposed. Expanding the common formulation of top-k to take into account the variance of tuples, var-k will be shown able to retrieve any potentially optimal point while retaining the properties that made top-k so widespread in the field.

Le query top-k lineari sono il più tipo di ranking query più comunemente implementato, essendo sia veloci da eseguire che capaci di soddisfare i bisogni dell'utente. Nonostante i suoi vantaggi, questo approccio alla ottimizzazione multi-obiettivo non è sempre ottimale, fallendo spesso nell'evidenziare tuple interessanti presenti all'interno della base di dati che sta venendo analizzata. Queste tuple posso essere identificate da un'altro tipo di query, le skyline query, che sono però lente e poco funzionali. In questa tesi, la capacità delle query top-k lineari nell'individuare tuple ottimali verrà analizzata, dapprima mediante appropriate metriche e indicatori calcolati su dati reali e poi attraverso un approccio teorico più rigoroso. Dopodichè, un nuovo tipo di query, la query Var-k, verrà proposta. Questa espande la comune formulazione delle query top-k prendendo in considerazione la varianza delle tuple e verrà dimostrato come sia capace di recuperare ogni punto potenzialmente ottimale pur mantenendo le proprietà che hanno reso le query top-k così largamente utilizzate in questo campo.