Résumer efficacement des flux de données massifs en fenêtre glissante

Autor: Nicoló Rivetti, Yann Busnel, Achour Mostefaoui
Přispěvatelé: Laboratoire d'Informatique de Nantes Atlantique (LINA), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), Gestion de Données Distribuées [Nantes] (GDD), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI), Dependability Interoperability and perfOrmance aNalYsiS Of networkS (DIONYSOS), RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-13-INFR-0003,SocioPlug,Cloud social sur des réseaux de plugs, pour un accès à l'information symétrique et respectueux de la vie privée(2013), ANR-10-LABX-0007,COMIN Labs,Digital Communication and Information Sciences for the Future Internet(2010), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Busnel, Yann, Infrastructures matérielles et logicielles pour la société numérique - Cloud social sur des réseaux de plugs, pour un accès à l'information symétrique et respectueux de la vie privée - - SocioPlug2013 - ANR-13-INFR-0003 - INFRA - VALID, Digital Communication and Information Sciences for the Future Internet - - COMIN Labs2010 - ANR-10-LABX-0007 - LABX - VALID
Jazyk: angličtina
Rok vydání: 2016
Předmět:
Zdroj: ALGOTEL 2016-18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications
ALGOTEL 2016-18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2016, Bayonne, France
HAL
Popis: Estimating the frequency of any piece of informa- tion in large-scale distributed data streams became of utmost importance in the last decade (e.g., in the context of network monitoring, big data, etc.). If some elegant solutions have been proposed recently, their approximation is computed from the inception of the stream. In a runtime distributed context, one would prefer to gather information only about the recent past. This may be led by the need to save resources or by the fact that recent information is more relevant.In this paper, we consider the sliding window model and propose two different (on-line) algorithms that approximate the items frequency in the active window. More precisely, we determine a (ε, δ)-additive-approximation meaning that the error is greater than ε only with probability δ. These solutions use avery small amount of memory with respect to the size N of the window and the number n of distinct items of the stream, namely, O(1/ε log 1/δ (logN+logn)) and O( 1/τε log 1/δ (logN+logn)) bits of space, where τ is a parameter limiting memory usage. We also provide their distributed variant, i.e., considering the sliding window functional monitoring model. We compared the proposed algorithms to each other and also to the state of the art through extensive experiments on synthetic traces and real data sets that validate the robustness and accuracy of our algorithms.
Estimer la fréquence de n'importe quel item dans des flux de données massifs est un des problèmes majeurs de la dernière décennie. Si plusieurs solutions élégantes ont été proposées récemment, leur approximation est calculée depuis le commencement du flux. Dans un contexte applicatif en ligne, il serait préférable de collecter l'information sur un passé récent, tant pour économiser des ressources que par pertinence de l'information la plus récente. Dans cet article, nous considérons le modèle dit de fenêtre glissante et proposons deux algorithmes en ligne qui estiment la fréquence de chaque item dans la fenêtre courante. Ces algorithmes sont des (ε, δ)-approximations absolues des valeurs de fréquences réelles, utilisant une faible quantité mémoire (respectivement O(1/ε log 1/δ (log N + log n)) et O(1/τε log 1/δ (log N + log n)) bits, où N est la longueur de la fenêtre, n est le nombre d'items distincts du flux et τ est un paramètre permettant de limiter l'utilisation mémoire. Les expérimentations conduites, comparant nos solutions à celles de l'état de l'art, illustrent la validité et la robustesse de nos algorithmes.
Databáze: OpenAIRE
Externí odkaz: