Τμημα Πληροφορικης Πανεπιστημιου Ιωαννινων

CSE.UOI :: MYE047 -- Αλγόριθμοι για Δεδομένα Ευρείας Κλίμακας

Ακαδημαϊκό Έτος 2019 -- 2020

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Γενικές Πληροφορίες

Διδάσκων: Σπύρος Κοντογιάννης
Email -- URL -- Voice:   --  http://www.cse.uoi.gr/~kontog/  --  (26510) 08812
URL Μαθήματος: http://www.cse.uoi.gr/~kontog/courses/Algorithms-For-Big-Data/
Ώρες Διαλέξεων: Κάθε Παρασκευή 09:00--12:00
Χώρος Διαλέξεων: ΑΙΘΟΥΣΑ Ι2, ισόγειο Κτιρίου ΤΜΗΥΠ
Ώρες Επικοινωνίας:

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Περιγραφή

Ο σχεδιασμός αλγορίθμων για την αποδοτική επεξεργασία συνόλων δεδομένων του πραγματικού κόσμου, θέτει νέες προκλήσεις τόσο λόγω του μεγέθους τους όσο και λόγω της μορφής παρουσίασής τους ως κύματα. Το μάθημα πραγματεύεται παραδείγματα αλγοριθμικών τεχνικών που επιτυγχάνουν την αποδοτική επεξεργασία δεδομένων ευρείας κλίμακας, τα οποία είναι αδύνατον να αποθηκευτούν στην κύρια μνήμη ή/και να επεξεργαστούν στην ολότητά τους, όταν εμφανίζονται με τη μορφή κύματος δεδομένων που μπορούμε να προσπελάσουμε μόνο μέσω ενός μικρού αριθμού περασμάτων. Το μάθημα θα ασχοληθεί με: Αλγοριθμικές τεχνικές δειγματοληψίας, φιλτραρίσματος, και στατιστικής επεξεργασίας κυμάτων, τεχνικών για παρασκευή περιλήψεων (sketches), δηλαδή, συμπαγών δομών δεδομένων που όμως παρέχουν ικανοποιητικές απαντήσεις για μετρικές του συνόλου δεδομένου. Τεχνικές μείωσης διάστασης, με διατήρηση της βασικής γεωμετρικής δομής. Αποδοτικές τεχνικές για την αριθμητική γραμμική άλγεβρα. Μεθόδους για αραίωση γραφημάτων και παραγωγή περιλήψεων γραφημάτων. Έλεγχο ιδιοτήτων του συνόλου δεδομένων μέσω δειγματοληψίας.

Ο φοιτητής / η φοιτήτρια που θα έχει ολοκληρώσει επιτυχώς το μάθημα θα πρέπει να είναι σε θέση να:

Αξιολόγηση του Μαθήματος

ΤΕΛΙΚΟΣ ΒΑΘΜΟΣ =  0.5*ΒΓΕ + 0.5*ΒΑΝ

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

 

Ανακοινώσεις

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό

 

Ημερολόγιο Μαθήματος (2019-20)

Διδακτική  Εβδομάδα Ημερομηνίες Διδασκαλίας Ύλη Εβδομάδας Συνοδευτικό Υλικό
Περιοχη Περιορισμενης Προσβασης
Διαφάνειες
password protected
Σημειώσεις
password protected
1η 14/02 Εισαγωγικά Μαθήματος.

Τεχνικές Αναζήτησης Όμοιων Αντικειμένων
* Μετρικές Ομοιότητας-Απόστασης Έγγράφων
* Shingling: Μεταροπή Εγγράφων σε Σύνολα

Διαφάνειες: Εισαγωγικά
[ανάγνωση/εκτύπωση]
 
2η 06/03 Τεχνικές Αναζήτησης Όμοιων Αντικειμένων
* Min-Hashing: Ομοιότητα Υπογραφών για Προσέγγιση Jaccard-Ομοιότητας
* Locality-Sensitive Hashing: Δημιουργία υποψήφιων για ομοιότητα ζευγών αντικειμένων
Διαφάνειες: Ομοιότητα Εγγράφων
[ανάγνωση/εκτύπωση]
 
3η 20/03 Αναζήτηση Συχνών Συνόλων Αντικειμένων
* Κανόνες Συσχέτισης
* Αλγόριθμοι Εντοπισμού Συχνών Συνόλων Αντικειμένων:
   -- Μέτρηση ζευγών με τριγωνικό μητρώο μετρητών.
   -- Μέτρηση ζευγών μέσω πίνακα κατακερματισμού.
Διαφάνειες
[ανάγνωση/εκτύπωση]
 
4η 27/03 Αναζήτηση Συχνών Συνόλων Αντικειμένων
* Αλγόριθμοι Εντοπισμού Συχνών Συνόλων Αντικειμένων:
   -- Αλγόριθμος A-Priori
   -- Αλγόριθμος PCY
   -- Εξειδικεύσεις του PCY (MultiStage - MultiHash)
* Αλγόριθμοι Εντοπισμού Συχνών Συνόλων με Δυο Περάσματα:
   -- Δειγματοληψία
   -- Αλγόριθμος SON
 
5η 03/03 Τεχνικές για επεξεργασία Ροών Δεδομένων.
* Δειγματοληψία Μεταβλητού Μήκους / Σταθερού Μήκους (Reservoir Sampling).
* Υπολογισμός Μερικών Αθροισμάτων σε Κυλιόμενα Παράθυρα.
* Υπολογισμός Μερικών Αθροισμάτων σε Κυλιόμενα Παράθυρα.
Διαφάνειες
[ανάγνωση/εκτύπωση]
 
6η 10/04 Τεχνικές για επεξεργασία Ροών Δεδομένων.
* Φίλτρα Bloom.
* Μέτρηση διαφορετικών στοιχείων σε ροή (αλγόριθμος Flajolet-Martin)
* Υπολογισμός στιγμών ως προς τις συχνότητες εμφάνισης στοιχείων στη ροή(αλγόριθμος AMS)
* Εκτίμηση συχνά εμφανιζόμενων στοιχείων σε ροή
Διαφάνειες
[ανάγνωση/εκτύπωση]
 
7η 08/05 Μείωση Διάστσης (πρώτο μέρος) Διαφάνειες
[ανάγνωση/εκτύπωση]
 
8η 15/05 Μείωση Διάστασης (δεύτερο μέρος)  
9η 22/05 Συσταδοποίηση Αντικειμένων Διαφάνειες
[ανάγνωση/εκτύπωση]
 
10η 29/05 Συστήματα Παροχής Συστάσεων Διαφάνειες
[1ο μέρος | 2ο μέρος]
 
11η 05/06 Επίλυση Αποριών    
---- ---- ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ:
-- Ώρα:
-- Αίθουσα: Ι2
-- Επιτρέπεται να έχετε μαζί σας το διδακτικό σύγγραμμα του μαθήματος

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

 

Χρήσιμο Υλικό

Βιβλιογραφία Μαθήματος

Τα βασικά εγχειρίδια του μαθήματος είναι:

  • Βιβλίο [22768468]: Εξόρυξη από μεγάλα σύνολα δεδομένων J. Leskovec, A. Rajaraman, and J. Ullman (v2, 2014)

  • Mining of Massive Datasets J. Leskovec, A. Rajaraman, and J. Ullman (v3 beta, 2018) free-online @ http://www.mmds.org

  • Βιβλίο [68386089]: Εξόρυξη και ανάλυση δεδομένων: Βασικές έννοιες και αλγόριθμοι MOHAMMED J. ZAKI, WAGNER MEIRA JR. (1η έκδοση, 2017)

  • Βιβλίο [77107675]: Εισαγωγή στην εξόρυξη δεδομένων Tan Pang – Ning, Steinbach Michael, Kumar Vipin (3η έκδοση, 2018)

  • Σημειώσεις/διαφάνειες του διδάσκοντος (θα δίνονται περιοδικά από το Ημερολόγιο του μαθήματος).

Ενδεικτικές Λύσεις Προόδων / Εξετάσεων (για αναφορά πιθανών λαθών παρακαλείστε να επικοινωνήσετε με τον διδάσκοντα):

  • 2018-19: 1η Ανάθεση -- 2η Ανάθεση -- 3η Ανάθεση -- 4η Ανάθεση -- Εξέταση Ιανουαρίου -- Εξέταση Σεπτεμβρίου

 

 

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Δημιουργία και συντήρηση σελίδας μαθήματος: Σπύρος Κοντογιάννηςς. Ημερομηνία τελευταίας αλλαγής: 10/06/2020.