Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

Πολυτεχνική Σχολή - Πανεπιστήμιο Ιωαννίνων

Αλγοριθμικές Τεχνικές για Δεδομένα Ευρείας Κλίμακας

Course Feature
Περιγραφή μαθήματος

Κωδικός μαθήματος: ΜΥΕ047

Εβδομαδιαίες ώρες διδασκαλίας: 3,0,2

Εξάμηνο σπουδών: >=6

Διδακτικές Μονάδες: 4

Μονάδες ECTS: 5

Ιστοσελίδα Μαθήματος:

Προσφερόμενο:

Προαπαιτούμενα:

Περιεχόμενο:

Επιλεγμένα θέματα από τις ακόλουθες περιοχές: Κυματισμός (streaming): Μελετώνται τεχνικές επεξεργασίας συνόλων δεδομένων που αποκαλύπτονται με τη μορφή κύματος. Ασχολούμαστε με τεχνικές προσέγγισης βασικών ιδιοτήτων του κύματος, αξιοποιώντας ένα πολύ μικρό αποτύπωμα της μνήμης. Για παράδειγμα θα ασχοληθούμε με τεχνικές δειγματοληψίας του κύματος, τεχνικές προσεγγιστικού υπολογισμού στατιστικών μετρήσεών του (π.χ., πλήθος διαφορετικών στοιχείων, συχνότητες εμφανίσεων στοιχείων, heavy hitters, κ.λπ.), καθώς και τεχνικές για προσεγγιστική επίλυση γραφοθεωρητικών προβλημάτων (π.χ., συνδεσιμότητα, αποστάσεις, μέγιστα ταιριάσματα), και τεχνικές φιλτραρίσματος του κύματος (πχ, φίλτρα Bloom). Σκιαγράφηση (sketching): Μελετώνται τεχνικές για τον υπολογισμό ενός προσεκτικά επιλεγμένου συνόλου μετρήσεων (η σκιαγράφηση) C(X) ενός συνόλου δεδομένων Χ, έτσι ώστε να είμαστε σε θέση να προσδιορίσουμε βασικές παραμέτρους του Χ από την ανάγνωση και μόνο της σκιαγράφησης C(X). Παρουσιάζονται αποτελέσματα για την παραγωγή p-σταθερών σκιαγραφήσεων, για αραιή ανάκτηση (sparse recovery) και έλεγχο ιδιοτήτων (property testing). Αλγόριθμοι για κύματα γραφημάτων: Ειδικά για περιπτώσεις όπου το κύμα δεδομένων αφορά ένα δυναμικά εξελισσόμενο γράφημα, μελετώνται μέθοδοι επίλυσης θεμελιωδών προβλημάτων για τα γραφήματα αυτά, όπως κοντινότερος γείτονας, συνδεσιμότητα, χρησμοί αποστάσεων, αραιωτές τομής/φάσματος (cut/spectral sparsifiers), ταιριάσματα και σκιαγραφήσεις γραφημάτων, κ.λπ. Ευαίσθητος ως προς την τοπικότητα κατακερματισμός(locality sensitive hashing): Μελετώνται τεχνικές για αποτίμηση της ομοιότητας αντικειμένων, την αναζήτηση συχνά εμφανιζόμενων συλλογών αντικειμένων, και τον εξαρτώμενο από τα δεδομένα κατακερματισμό. Μείωση διάστασης: Μελετάται το θεμελιώδες Λήμμα των Johnson-Lindenstrauss, και τεχνικές για προσέγγιση μητρώων από μητρώα μικρού βαθμού (π.χ., principal component analysis, SVD, CURE). Έλεγχος απαιτήσεων επικοινωνίας: Μελετώνται βασικά προγραμματιστικά μοντέλα (π.χ., MapReduce, Hadoop) για τη σχεδίαση αλγορίθμων που προορίζονται για μοντέρνα υπολογιστικά περιβάλλοντα που εκτελούνται σε αποκεντρωμένους υπολογιστές, στοχεύοντας στην ελαχιστοποίηση των απαιτήσεων αλληλεπίδρασης μεταξύ των υπολογστικών πόρων. Η σκιαγράφηση γραφήματος είναι μια τεχνική που βοηθά σημαντικά προς αυτή την κατεύθυνση, ιδιαίτερα αν πρέπει να επεξεργαστούμε δυναμικά μεταβαλλόμενα γραφήματα.

Παρατηρήσεις: