------------------------------------------------------------------------- DATABASE SEMINAR ------------------------------------------------------------------------- Peter Wood, Birkbeck, University of London ------------------------------------------------------------------------- Top-k query answering with aggregation constraints and cached views ------------------------------------------------------------------------- Friday, May 31, 2013 -- h 12:00 **** Sala riunioni **** Dipartimento di Ingegneria Sezione di Informatica e Automazione Universita' Roma Tre Via Vasca Navale, 79 primo piano -------------------------------------------------------------------------- ABSTRACT Top-k query processing has recently received a significant amount of attention due to its wide application in information retrieval, multimedia search and recommendation generation. Our interest in this area arises from wanting to develop algorithms for recommending packages of items, rather than single items, to users, such as might be useful in travel planning. To do so, we also need to consider rank-join algorithms. We show that aggregation constraints can enrich the semantics of rank-join queries, by al- lowing users to impose their application-specific preferences in a declarative way. By analysing the properties of aggregation constraints, we develop efficient algorithms which can push the aggregation constraints inside the rank-join framework. We also consider the problem of how to answer a top-k query by using previously cached query results. Previous algorithms for this problem suffer from either limited scope or lack of scalability. We propose two novel algorithms for handling this problem, one which reduces the number of expensive linear programming problems that need to be solved, and the second which uses a space partition-based index structure. Through extensive experiments on various datasets, we demonstrate that our algorithms significantly outperform the state of the art. ----------------------------------------------------------------------------- Peter Wood obtained his BSc and MSc in Computer Science from the University of Cape Town (UCT), South Africa. He obtained a PhD in Computer Science in 1989 from the University of Toronto. He then spent nine years back at UCT, before joining King's College London in 1998. He moved to Birkbeck in 2001. His main interests throughout this time have been in query languages and the efficient evaluation of queries, including graph-based languages, visual languages, Datalog and XPath. He has also done some work on ECA languages, graph algorithms, XML compression, and most recently on top-k queries applied to recommender systems.