1. ASAP Top-k Query Processing in Unstructured P2P Systems
- Author
-
Reza Akbarinia, William Kokou Dedzoe, Philippe Lamarre, Patrick Valduriez, Akbarinia, Reza, Laboratoire d'Informatique de Nantes Atlantique (LINA), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Complex data management in distributed systems (ATLAS), Université de Nantes (UN)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Scientific Data Management (ZENITH), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Inria Sophia Antipolis - Méditerranée (CRISAM)
- Subjects
Waiting time ,[INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB] ,Theoretical computer science ,Computer science ,media_common.quotation_subject ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Response time ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,02 engineering and technology ,020204 information systems ,Formal specification ,0202 electrical engineering, electronic engineering, information engineering ,Peer to peer computing ,[INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB] ,020201 artificial intelligence & image processing ,Quality (business) ,Baseline (configuration management) ,media_common - Abstract
International audience; Top-k query processing techniques are useful in unstructured peer-to-peer (P2P) systems, to avoid overwhelming users with too many results. However, existing approaches suffer from long waiting times. This is because top-k results are returned only when all queried peers have finished processing the query. As a result, query response time is dominated by the slowest queried peer. In this paper, we address this users' waiting time problem. For this, we revisit top-k query processing in P2P systems by introducing two novel notions in addition to response time: the stabilization time and the cumulative quality gap. Using thèse notions, we formally define the as-soon-as-possible (ASAP) top-k processing problem. Then, we propose a family of algorithms called ASAP to deal with this problem. We validated our solution through implementation and extensive experimentation. The results show that ASAP significantly outperforms baseline algorithms by returning final top-k result to users in much better times.
- Published
- 2010