BD 4

Streaming

Peut-on garder peu de données, parmi celles qui sont lues dans un flux de données?
Exemple 1: Flux de valeurs: 1, 3, 6, 45, 3, 1, 3, 7, 3, .....
- Nombre de valeurs distinctes? F₀ = 5
  - Recherche de collision
  - MinHash
- Valeurs les plus fréquentes: Top-k avec SpaceSaving
Exemple 2: Flux d'arêtes: (a,b), (b,c), (c,d), (a,c)......
- Le graphe est-il connexe?
- Il y a-t-il des clusters?
- Réservoir sampling: toutes les arêtes ont la même probabilité d'étre dans le Réservoir.
- Window Réservoir: données dynamiques
- Graphes aléatoires: émergence de la composante géante.
Flux Twitter sur des mots clés
- Visualisation Gephi
- Flux de mégadonnées
- Programme Python qui implémente le Réservoir sampling (k= taille du Réservoir)

 import random

 import csv

 .......à définir pour lire un fichier


 edge_list = read_edge_from_file(file_input)

 #m stores the number of edges in windows. m[0] is the number of edges in the first window

 m=[0]

 #i is the index of the windows: 0,1,2,...

 i=0

 sample = []

 for index, edge in enumerate(edge_list):

    m[i] += 1

    if index < k:

        sample.append(edge)

    else:

        j = random.randint(0, index)

        if j < k:

           del sample[j]

           sample.append(edge)


 print(sample)

Code Réservoir lisant dt_b.csv

Fichier dt_b.csv

UP2