Solution compacte aux requêtes d'appartenance sur des flux de données

Yann Busnel (1, 2) , Noël Gillet (1, 2)

1 IMT Atlantique - SRCD - Département Systèmes Réseaux, Cybersécurité et Droit du numérique
2 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires

Le test d'appartenance est fondamental en informatique. Plus formellement, si on considère un sous-ensemble d'éléments appartenant à un univers, nous voulons pouvoir répondre à la question "étant donné tout élément de l'univers, celui-ci appartient-il au sous-ensemble en question ?". Interroger un oracle parfait est très coûteux en pratique (temps de recherche long, latence importante, etc.), il est ainsi intéressant d'interroger dans un premier temps une structure compacte, comme le classique filtre de Bloom, qui représente le sous-ensemble considéré. L'oracle ne sera ainsi interrogé que dans certains cas prédéfinis. Dans cet article, nous proposons une amélioration de cette méthode dans le cadre de l'analyse de flux de données à grande échelle. L'idée consiste à construire ledit filtre en temps réel, en y stockant uniquement les éléments du flux qui appartiennent au sous-ensemble. Pour cela, l'oracle n'est interrogé que si un élément est vu pour la première fois, afin de déterminer son appartenance à l'ensemble. Nous présentons des garanties théoriques ainsi qu'un ensemble de simulation justifiant l'intérêt de notre travail.

Mots clés: Flux de données; Requête d’appar...; Filtre de Bloom

Domaines: Algorithme et structure de données [cs.DS]

Yann Busnel, Noël Gillet. Solution compacte aux requêtes d'appartenance sur des flux de données. ALGOTEL 2020 – 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2020, Lyon, France. ⟨hal-02869558⟩