Section outline

  • Διάλεξη 9/4: Heavy-Hitters σε Ροές Δεδομένων και Εύρεση Κοντινών Γειτόνων

    • Eπεξεργασία ροών δεδομένων (data streams): εκτίμηση συχνότητας εμφάνισης συχνών στοιχείων (heavy-hitters), αλγόριθμοι lossy counting και count-min sketch (προτείνεται να μελετήστε ακόμη τις σημειώσεις εδώ και εδώ, και να δείτε τις διαφάνειες εδώ, εδώ και εδώ).
    • Εύρεση κοντινών γειτόνων: ορισμός προβλήματος, επεξεργασία κειμένων, shingling, min-hashing, locality sensitive hashing.  

    Προτεινόμενη μελέτη: 

    Περαιτέρω μελέτη για επεξεργασία ροών δεδομένων:

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

    Σύνδεσμος στη βιντεοσκοπημένη διάλεξη (απαιτείται συνθηματικό)

    (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο.)