14.00, room 445, PCRI

Abstract
We present in this talk our recent research on top-k query answering in social applications.

This problem requires a significant departure from socially agnostic techniques for information retrieval. One can now exploit the social links in order to obtain more relevant results, valid not only with respected to the keyword query but also with respect to the social context of the user who issued it. We propose a sound and complete algorithm, called TOPKS, which addresses important applicability issues of existing techniques. Moreover, we show that TOPKS is instance optimal in the case when the search relies exclusively on the social weight of the data. To further address the efficiency needs of online applications, for which the exact search, albeit optimal, may still be expensive, we also consider approximate algorithms. These rely on concise statistics about the social network or on approximate shortest-paths computations.

As a complementary direction for efficient, online answering, we also consider the materialization and exploitation of previous query results (views). We study social-aware query optimization based on views, presenting algorithms that address two important sub-problems. First, handling the possible differences in context between the various views and an input query leads to view results having uncertain scores, i.e., score ranges valid for the new context. As a consequence, current top-k algorithms are no longer directly applicable and need to be adapted to handle this uncertainty. Second, adapted view selection techniques are needed, which can leverage both the descriptions of queries and statistics over their results.

Extensive experiments on both synthetic and real-world data (from Delicious and Twitter) show that our techniques have the potential to scale and meet the requirements of real applications. They have been recently demonstrated in a prototype social-aware search called Taagle.

This is joint work with Silviu Maniu (now at Hong Kong University).

Short bio
Bogdan Cautis is an Associate Professor at the Computer Science and Networks Department of Télécom ParisTech, since October 2007. He received his Habilitation (HdR) in March 2012, from Universite Pierre et Marie Curie and his Ph.D. in September 2007 from the University of Paris XI — working in the Gemo research team of INRIA Futurs, advised by INRIA DR Serge Abiteboul and Tova Milo from Tel Aviv University. His recent research interests lie in the broad area of Web data management and information retrieval: data management on the Web, data extraction, social networks, search, recommender systems, XML and semi-structured databases.

14.00, room 445, PCRI

Abstract
With the rapid growth of data sources, services and devices connected to the Internet, online available web content is getting more and more diverse and dynamic. In order to facilitate the efficient dissemination of evolving and temporary information, many web applications publish their new information as RSS and Atom documents which are then collected and transformed by RSS aggregators like Google Reader or Yahoo! News. I address the particular issue of large-scale aggregation of highly dynamic information sources by focusing on the design of optimal refresh strategies for large collections of RSS feed documents.

First, I introduce two quality measures specific to RSS aggregation which reflect the information completeness and average freshness of the result feeds. Then, I propose a best-effort feed refresh strategy that achieves maximum aggregation quality compared with all other existing policies with the same average number of refreshes. This strategy is based on specific online change estimation models developed after a deep analysis of the temporal publication characteristics of a representative collection of real-world RSS feeds. The presented methods have been implemented and tested against synthetic and real-world RSS feed data sets.

14.30, room 445, PCRI

Abstract
The skyline operator (aka Pareto front) extracts relevant records from multidimensional databases according to multiple criteria. This operator has received a lot of attention because of its ability to identify the best records in a database without requiring to specify complex parameters like the relative importance of each criterion (as it is done in ranking methods). However, recent attempts to apply the operator to real data analysis tasks have revealed some weaknesses of the original definition.

In this presentation I will introduce the skyline operator, indicate some recent research trends related to these weaknesses and focus on the so-called aggregate skyline queries, where the skyline is executed on sets of records instead of single items. This operator can be used to express queries in the form: return the best groups depending on the features of their elements, and thus provides a powerful combination of grouping and skyline functionality.

I will conclude the presentation by showing an application of the skyline operator to complex data representing multiple social networks.

Short bio
Matteo Magnani graduated in Computer Science at the University of Bologna in 2002. He studied at the University of Marne la Vallée (undergraduate level) and the Imperial College London (postgraduate research level). In 2006 he obtained a PhD in Computer Science (Bologna) where in 2011 he also graduated in Violin. He has received a Rotary Prize for the best student of the Science Faculty (UniBO), a Best Paper Award at ASONAM 2011, a Funniest Presentation award at SBP 2010 and his mother is very proud of him (or at least this is what she officially says). Until May 2012 he was a researcher (RTD) at the Dept. of Computer Science, University of Bologna and he currently holds a position at research assistant professor level at the Data Intensive Systems group, Dept. of Computer Science, Aarhus University, Denmark.

His main research interests span Database and Information Management systems, specifically uncertain information management and multidimensional database queries, and Social Computing/Complex Network Science. He has written around 1.5 Kg of papers on these topics (when printed on heavy A4 size sheets). He is currently the joint coordinator of the #sigsna research group on social network analysis, and has successfully attracted funding from Working Capital (Telecom Italia), PRIN and FIRB (MIUR – Italian Ministry for education, University and Research) schemes.