Το μάθημα αφορά σε αλγόριθμους εξόρυξης, επεξεργασίας και ανάλυσης δεδομένων που προέρχονται από πολύ μεγάλα σύνολα δεδομένων, δηλαδή δεδομένων τόσο μεγάλου όγκου που δεν χωρούν στην κύρια μνήμη. Λόγω της έμφασης στο μέγεθος, πολλά από τα παραδείγματα αφορούν στον Παγκόσμιο Ιστό ή σε δεδομένα που προέρχονται από τον Παγκόσμιο Ιστό. Κύριος στόχος είναι να παρουσιαστούν αλγόριθμοι εξόρυξης, επεξεργασίας και ανάλυσης δεδομένων με συστηματικό τρόπο, που περιλαμβάνει αποδείξεις ορθότητας και υπολογιστικής πολυπλοκότητας. Τα βασικά θέματα που καλύπτονται είναι:
Frequent Itemsets Mining: Εξόρυξη κανόνων συσχέτισης και συνόλων στοιχείων που εμφανίζονται συχνά σε μεγάλα δεδομένα. Αλγόριθμος A-priori. Χρήση hashing, αλγόριθμοι PCY, SON, Toivonen. Παραγωγή και αξιολόγηση κανόνων συσχέτισης. Αλγόριθμος FP-Growth.
Τεχνικές συσταδοποίησης: Η “κατάρα” των πολλών διαστάσεων, Ιεραρχική συσταδοποίηση, ο αλγόριθμος K-means και ο αλγόριθμος BFR. Συσταδοποίηση με αντιπροσώπους, αλγόριθμος CURE. Πλεονεκτήματα και μειονεκτήματα των μεθόδων.
Ανάλυση υπερσυνδέσμων (link analysis): Ορισμός του αλγορίθμου PageRank, δομή του Παγκόσμιου Ιστού, μέθοδος Power Iteration, αποφυγή αδιεξόδων, δομές spider traps (παγίδες αράχνης) και η μέθοδος Taxation. Αποτελεσματικός υπολογισμός του PageRank, αποτελεσματικές προσεγγίσεις για το PageRank Iteration. RandomTeleports (τυχαίες τηλεμεταφορές), υπολογισμός PageRank (διαμόρφωση πινάκων, επαναπροσδιορισμός της εξίσωσης, διαμόρφωση και κωδικοποίηση αραιών πινάκων, Block stripe ανάλυση). Topic Specific PageRank(κατάταξη ιστοσελίδων σύμφωνα με το θέμα), μέτρηση της εγγύτητας σε γράφους, αλγόριθμοι SimRank, WebSpam, Term Spam, Spam Farming, Link Spamming, TrustRank, SpamMass, Hubs and Authorities (αλγόριθμος HITS).
Κατακερματισμός (Hashing): Κλειστή και ανοιχτή διευθυνσιοδότηση. Καθολικές οικογένειες συναρτήσεων κατακερματισμού. Αλυσίδωση. Παράγοντας φόρτου και ανάλυση χρόνου εκτέλεσης βασικών πράξεων. Ανοιχτή διευθυνσιοδότηση. Γραμμική και τετραγωνική διερεύνηση. Διπλός κατακερματισμός. Παράγοντας φόρτου και ανάλυση χρόνου εκτέλεσης βασικών πράξεων. Τέλειος κατακερματισμός. Κατακερματισμός “κούκου” (cuckoohashing).
Συστήματα συστάσεων: Το φαινόμενο “Long Tail”, utility matrix (πίνακας χρησιμότητας), συστήματα συστάσεων με βάση το περιεχόμενο, προφίλ στοιχείου, προφίλ χρήστη. Συνεργατικό φιλτράρισμα, εύρεση παρόμοιων χρηστών, πρόβλεψη αξιολόγησης, χρήστης - χρήστης , αντικείμενο – αντικείμενο. Υβριδικές μέθοδοι, συνδυασμός συνολικής εκτίμησης βάσης και συνεργατικού φιλτραρίσματος.
Εντοπισμός κοινοτήτων (Community Detection): Εισαγωγή στο πρόβλημα. Μετρικές Edge Betweeness και Modularity. Αλγόριθμος Girvan-Newman. Αλγόριθμος Louvain. Εντοπισμός κοινοτήτων μέσω ιδιοτιμών γράφων, spectral clustering.
Διαφήμιση στο web: Άμεσοι (online) αλγόριθμοι, άπληστοι αλγόριθμοι, competitive ratio, Matching problem(πρόβλημα ταιριάσματος), πρόβλημα Adwords, αλγόριθμος Balance.