Section outline

  • 28/3: Ροές Δεδομένων

    • Επεξεργασία ροών δεδομένων (streams): Δειγματοληψία από ροή δεδομένων, reservoir sampling (διαφάνειες, 11-21), εκτίμηση συχνότητας εμφάνισης συχνών στοιχείων, αλγόριθμοι lossy counting και count-min sketch (μελετήστε τις σημειώσεις εδώ και εδώ, και τις διαφάνειες εδώ και εδώ).
    • Εύρεση παρόμοιων αντικειμένων: επεξεργασία κειμένων, shingling (διαφάνειες, 1-24). 
      Προτεινόμενη μελέτη: [MMDS] 3.1, 3.2. 


    Περαιτέρω μελέτη για ροές δεδομένων:

    • Σημειώσεις και βιβλίο του S. Muthukrishnan.
    • Η εργασία των Manku και Motwani όπου παρουσιάζεται ο αλγόριθμος lossy counting. 
    • Η εργασία των Cormode και Muthukrishnan όπου παρουσιάζεται ο αλγόριθμος count-min sketch.