Outils logiciels pour les cours Paris II

Cours Paris II

Stages/ Thèses/ Séminaires

Laboratoire

edit SideBar

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? F0 = 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