Seminar on Skyline and Top-k Queries in Distributed and Parallel Environments by Christos Doulkeridis

Time: Tuesday 17th November 2009, 10:00
Place: Aalborg University, Selma Lagerløfs vej 300, room 02.13

Abstract:

Skyline and top-k queries have received considerable attention in database research lately. A challenging problem is to efficiently compute such queries in non-centralized domains, such as widely distributed systems or parallel architectures.

In this talk, I will present some solutions to this problem, exploiting as key observation that there exists an inherent relationship between skyline queries and top-k queries, as the skyline set contains all objects for any top-1 monotone function. In the first part of the talk, I will present the SPEERTO framework for top-k query processing in large-scale super-peer networks, under the assumption of horizontal data distribution over the peers. Relying on a thresholding scheme, SPEERTO returns the exact results progressively to the user, while the number of queried super-peers and transferred data is minimized. In the second part of the talk, I will focus on skyline computation in a parallel shared-nothing architecture. A novel data partitioning scheme will be presented for splitting data objects to servers, which greatly improves the performance of each server by dividing the workload fairly over the participating servers. By discussing the experimental results, the efficiency of the proposed partitioning scheme will be demonstrated.

Short bio:
Christos Doulkeridis is a post-doctoral researcher under an “Alain Bensoussan” fellowship in the Norwegian University of Science and Technology (NTNU) in the group of professor Kjetil Noervaag. In 2007 he received his PhD entitled “Organizing and Searching Data in Unstructured P2P Networks” in the Department of Informatics, Athens University of Economics and Business (AUEB), under the supervision of associate professor Michalis Vazirgiannis. Prior to this, he received a Master of Science in Information Systems at the Athens University of Economics and Business (AUEB, 2003) and a Diploma from the department of Electrical Engineering at the National Technical University of Athens (NTUA, 2001). His research interests include data management in peer-to-peer systems, distributed knowledge discovery, mobile and context-aware computing, web services and semi-structured data.