Langues : English français
Accueil > Manifestations > Thèses et HDR > Thèses > William Kokou DEDZOE

William Kokou DEDZOE

Directeur de thèse

Patrick Valduriez
Philippe Lamarre

Résumé

Dans les communautés virtuelles pair-à-pair (P2P) de partage de
données, les requêtes top-k présentent deux avantages principaux.
Premièrement, elles permettent aux participants de qualifier les résultats
de leurs requêtes par rapport aux données partagées dans le système et
ceci en fonction de leurs préférences individuelles. Deuxièmement, elles
évitent de submerger les participants avec un grand nombre de réponses.
Cependant, les techniques existantes pour le traitement des requêtes top-k
dans un environnement complètement distribué présentent l’inconvénient
d’un temps d’attente important pour l’utilisateur. Ce temps d’attente est
encore très long plus le système est surchargé. Dans un premier temps,
nous revisitons le problème du temps d’attente de l’utilisateur dans le
traitement des requêtes top-k en introduisant deux nouvelles mesures : le
temps de stabilisation et la qualité restante cumulée. En complément des
mesures existantes, elles permettent de qualifier plus précisément le
comportement d’un algorithme top-k. Dans un deuxième temps, nous proposons
une famille d’algorithmes (ASAP), permettant de retourner à l’utilisateur
les résultats de bonne qualité le plus tôt possible. Enfin, nous nous
intéressons au problème du traitement des requêtes top-k dans le cadre des
systèmes P2P surchargés, particulièrement critique pour les solutions
classiques, en proposant une nouvelle approche (QUAT). Cette solution fait
usage de descriptions synthétiques des données des pairs pour permettre
aux pairs de traiter en priorité les requêtes pour les quelles ils peuvent
fournir des résultats de bonne qualité.

Mots-clés : Communautés virtuelles, Systèmes pair-à-pair, Traitement de
requêtes, Temps de réponse, Temps de stabilisation, Qualité restante
cumulée, Description synthétique d’un pair.

Abstract :

Top-k queries have two main advantages for peer-to-peer (P2P)
data sharing virtual communities. First, they allow participants to rank
the results for their queries based on the existing data in the system as
well as on their own preferences. Second, they avoid overwhelming
participants with too many results. However, existing top-k query
processing techniques for P2P systems make users suffer from long waiting
times. This becomes even more problematic in overloaded P2P systems. In
this thesis, we first revisit the top-k query processing problem and
introduce two new measures : the stabilization time and the cumulative
quality gap. These two novel measures, in addition to existing measures,
allow for better evaluating the behavior of top-k query processing
techniques. We then propose a new family of top-k query processing
techniques (ASAP) that allows to return high quality results as soon as
possible. Finally, we study the problem of top-k query processing in
overloaded systems. As a result, we propose a new approach, called QUAT,
that relies on synthetic data descriptions of peers in order to allow
peers to prioritize queries for which they can provide high quality
results.

Keywords : Virtual communities, Peer-to-Peer systems, Top-k query
processing, Response time, Stabilization time, cumulative quality gap,
Peer synthetic description.

Dernière modification : lundi 28 novembre 2011