Reducing Uncertainty in Top-K Queries

by Davide Martinenghi, Milan Politecnico

November 21st 2013 @ 14:00, in Garda

In this invited talk Davide Martinenghi will present his work about

Reducing Uncertainty in Top-K Queries


Finding the best answers to a query is a problem of paramount importance in many scenarios, including big data analysis, Web queries, and several other data-centric contexts. A common hindrance to this task comes from an inherent amount of uncertainty that may reside both in the data at hand (e.g., due to unreliability of data sources) and in the query (e.g., in the relative importance of some attributes of the queried sources). Uncertain answers entail uncertain ranking, i.e., there is no consensus on how to rank the tuples in the query answer. One way to cope with this problem is to determine the most representative ranking out of the possible orderings compatible with an uncertain scenario. Orthogonally, one can also try to reduce the amount of uncertainty by asking questions to human users in order to disambiguate the mutual order of some answer tuples. After discussing top-K query answering in the presence of uncertainty, we shall illustrate suitable strategies for exploiting the availability of a crowd of humans by determining which questions to ask and which users to select.


Davide Martinenghi is an assistant professor at the Dipartimento di Elettronica, Informazione e Bioingegneria of Politecnico di Milano, Italy.

Previously, he was a research fellow at the Free University of Bozen-Bolzano. He holds a PhD in Computer Science from Roskilde University, Denmark, and a M.Sc. in Computer Engineering from Politecnico di Milano. Before his PhD, he has been working as a software engineer in France and Italy. His main research interests include data integrity maintenance, Web data access, top-k query optimization, and, in a broad sense, applications of logic to data management. He is the author or coauthor of over 70 publications in these research areas. He has served in the Program Committee of several international conferences and workshops, and as Program Chair or Co-Chair for several workshops on data management.