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, ισόγειο Κτιρίου ΤΜΗΥΠ
Ώρες Επικοινωνίας:	Your browser does not support inline frames or is currently configured not to display inline frames.

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

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

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

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

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

Το μάθημα θα αξιολογηθεί μέσα από μια σειρά (3) αναθέσεις για το σπίτι, και μια τελική γραπτή εξέταση. Οι αναθέσεις θα είναι ανά 3 εβδομάδες και θα αφορούν είτε θεωρητικές ασκήσεις, ή κάποιες απλές προγραμματιστικές αναθέσεις. Οι αναθέσεις είναι υποχρεωτικές και θα διεκπεραιώνονται είτε ατομικά, ή σε ζευγάρια, ενώ ο μέσος βαθμός τους θα προσμετράται (τουλάχιστον) 50% τουτελικού βαθμού του μαθήματος. Δηλαδή, αν
- ΣΥΜ = Ενεργή συμμετοχή στις διαλέξεις (τακτική παρακολούθηση, απορίες, απαντήσεις σε ερωτήσεις, κ.λπ.)
- ΒΓΕ = Βαθμός γραπτής εξέτασης
- ΒΑΝ = Σταθμισμένος βαθμός αναθέσεων, και
τότε ο τελικός βαθμός του μαθήματος υπολογίζεται ως εξής:

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

Σε περίπτωση αποτυχίας, ο ΙΔΙΟΣ κανόνας θα ισχύσει και για την επαναληπτική εξέταση του Σεπτεμβρίου. Οι βαθμολογίες των αναθέσεων για το σπίτι ΔΕ ΜΕΤΑΦΕΡΟΝΤΑΙ για το επόμενο έτος, σε περίπτωση αποτυχίας.

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

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

10/06/2020: Για τις ανάγκες της επικείμενης εξ αποστάσεως εξέτασης του ΜΥΕ047, η οποία είναι προγραμματισμένη για τις 8 Ιουλίου 2020 στις 15:00-18:00, δημιουργήθηκε στο MS TEAMS η πιστοποιημένη αίθουσα εξέτασης με τίτλο "ΜΥΕ047 -- ΠΙΣΤΟΠΟΙΗΜΕΝΗ ΑΙΘΟΥΣΑ ΕΞΕΤΑΣΗΣ". Ήδη έχουν προσκληθεί στη συγκεκριμένη αίθουσα οι φοιτητές / φοιτήτριες που: (ι) εμφανίζονται στη λίστα φοιτητών/φοιτητριών προς εξέταση στο Ηλεκτρονικό Φοιτητολόγιο. (ιι) έχουν ήδη ιδρυματικό λογαριασμό email (cs...@uoi.gr) και μπορούν να ταυτοποιηθούν (άρα και να συμμετάσχουν στην πιστοποιημένη αίθουσα εξέτασης). Οι φοιτητές με ΑΜ 1485, 1640, 1884, 2345, παρ' ότι περιλαμβάνονται στη λίστα προς εξέταση φοιτητών του μαθήματος, δεν κατέστη δυνατόν να εντοπιστούν μέσω του ιδρυματικού τους λογαριασμού, και ως εκ τούτου δεν συμπεριλήφθηκαν στους συμμετέχοντες στην εξέταση. Αν πάντως κάποιος από αυτούς θεωρεί ότι θα έπρεπε να συμμετάσχει στην εξέταση, θα πρέπει να έρθει ΑΜΕΣΑ σε επικοινωνία με τον διδάσκοντα (στέλνοντας μήνυμα στο kontog@uoi.gr), προκειμένου να εξακριβωθεί ότι πράγματι δικαιούται να συμμετάσχει στην εξέταση και να συμπεριληφθεί στην πιστοποιημένη αίθουσα εξέτασης. Η εξ αποστάσεως γραπτή εξέταση θα γίνει μέσω μιας ηλεκτρονικής φόρμας υποβολής ερωτημάτων. Τα ερωτήματα αυτά θα είναι πολλαπλής επιλογής (με θετική / αρνητική βαθμολόγηση των απαντήσεων), καθώς και ερωτήματα ανάπτυξης όπου θα δίνετε μια σύντομη απάντησή σας σε προκαθορισμένο χώρο. Περισσότερα θα αναφερθούν σε επόμενα μηνύματα του διδάσκοντα στο ecourse του μαθήματος, σχετικά με τις εξετάσεις. Η βαθμολόγηση κάθε ανάθεσης για το σπίτι θα γίνει με βάση: (ι) Τον κώδικα υλοποίησης, τα πειραματικά αποτελέσματα και την τεχνική αναφορά εργασίας που παρέδωσαν οι φοιτητές. (ιι) Ενδεχόμενη προφορική εξέταση που θα γίνει, κατά την κρίση του διδάσκοντα, σχετικά με τις εργασίες που παραδόθηκαν. Υπενθυμίζεται τέλος ότι η συνολική αξιολόγηση του μαθήματος απαρτίζεται από τις δυο υποχρεωτικές αναθέσεις για το σπίτι, και την επίσης υποχρεωτική τελική γραπτή εξέταση.
18/05/2020: Στο αρχείο ερωτήσεων-απαντήσεων της 2ης ανάθεσης υπάρχουν συγκεντρωτικές απαντήσεις στις απορίες που έχουν προκύψει μέχρι στιγμής. Επιπρόσθετα, έγινε και μια μικρή επικαιροποίηση της εκφώνησης της 2ης ανάθεσης για το σπίτι, όπου μεταξύ άλλων δόθηκε περισσότερος χρόνος για την υλοποίηση της (νέα ημερομηνία παράδοσης: 5 Ιουνίου 2020).
06/05/2020: Ανακοινώθηκε ήδη η 2η ανάθεση για το σπίτι, με ημερομηνία παράδοσης την Παρασκευή 27/5/2020. Σχετική ανακοίνωση έχει γίνει και στο ecourse του μαθήματος.
26/03/2020: Η προθεσμία παράδοσης της 1ης ανάθεσης για το σπίτι παρατείνεται μέχρι την Τρίτη 31/03/2020, οποιαδήποτε ώρα. Επίσης, παρακαλούνται οι φοιτητές / φοιτήτριες που συμμετέχουν στο μάθημα να μελετήσουν προσεκτικά το αρχείο ερωτήσεων-απαντήσεων της 1ης ανάθεσης, όπου προστέθηκε ερώτημα σχετικά με τη διαδικασία της πειραματικής αξιολόγησης (ΕΡ10).
22/03/2020: Παρακαλούνται οι φοιτητές του μαθήματος να κατεβάσουν ξανά και να μελετήσουν πολύ προσεκτικά την εκφώνηση της 1ης ανάθεσης για το σπίτι, όπου έγινε μια πιο αναλυτική παρουσίαση της περιγραφής του πειραματικού μέρους (ενότητα 1ζ).
21/03/2020: Παρακαλούνται οι φοιτητές του μαθήματος να δούνε το αρχείο ερωτήσεων-απαντήσεων της 1ης ανάθεσης για το σπίτι, διότι έγινε μια σημαντική αλλαγή στην απάντηση του ΕΡΩΤΗΜΑΤΟΣ 9 (ευχαριστώ θερμά τη φοιτήτρια για την επισήμανση του λάθους).
19/03/2020: Οι φοιτητές του μαθήματος προτείνεται να μελετήσουν προσεκτικά το αρχείο ερωτήσεων-απαντήσεων σχετικά με την 1η ανάθεση. Έχουν γίνει ορισμένες σημαντικές προσθήκες ερωτήσεων-απαντήσεων που αφορούν την υλοποίηση των ρουτίνων MinHash και LSH, οι οποίες ενδεχομένως φανούν χρήσιμες
16/03/2020: Την προσεχή Παρασκευή, 20/03/2020, πρόκειται να γίνει η πρώτη εξ αποστάσεως διάλεξη του μαθήματος ΜΥΕ047. Για περισσότερες πληροφορίες σχετικά με τον τρόπο σύνδεσης, δείτε αυτή την ανακοίνωση στο ecourse του μαθήματος.
16/03/2020: Στο ecourse του μαθήματος έχει ήδη αναρτηθεί συνοδευτικό υλικό για την 1η ανάθεση για το σπίτι, ενώ έχει ήδη γίνει και επικαιροποίηση της εκφώνησης (κατεβάστε την ξανά και μελετήστε την προσεκτικά -- ενδέχεται να χρειάζεται ΑΝΑΝΕΩΣΗ για να δείτε το καινούργιο κείμενο). Επίσης, δημιουργήθηκε ένα αρχείο ερωτήσεων-απαντήσεων σχετικά με την 1η ανάθεση. Το αρχείο αυτό θα επικαιροποιείται τακτικά, ανάλογα με τις ερωτήσεις που υποβάλλονται, ώστε να είναι στη διάθεση όλων των φοιτητών οι απαντήσεις που δίνονται.
06/03/2020: Ανακοινώθηκε η πρώτη ανάθεση για το σπίτι, με ημερομηνία παράδοσης την Παρασκευή 27/3/2020.

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

Ημερολόγιο Μαθήματος (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.