Συντάχθηκε 30-09-2014 14:10
από Esthir Gelasaki
Email συντάκτη: egelasaki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Γεώργιου Μαντάκου
με θέμα
Ανάπτυξη Παράλληλου Συστήματος Για Εξαγωγή Υπογράφων
Τετάρτη 1 Οκτωβρίου 2014, 13:15
Αίθουσα 145π42, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Ιωάννης Παπαευσταθίου (επιβλέπων)
Καθηγητής Απόστολος Δόλλας
Καθηγητής Μίνως Γαροφαλάκης
Περίληψη
Η εξόρυξη πληροφορίας από δεδομένα αποθηκευμένα σε μορφή γράφων (graph mining) βρίσκει πρακτική εφαρμογή σε πολλές περιοχές (molecular substructure discovery, web link analysis, fraud detection, social network analysis). Καθώς αυξάνεται ο όγκος των δεδομένων αυτών, ενώ συσσωρεύεται συνεχώς καινούργια πληροφορία, αυξάνεται μαζί του και η ανάγκη για αποδοτικότερη και γρηγορότερη εξόρυξη.
Το πρόβλημα που έχουν να λύσουν αυτοί οι αλγόριθμοι συνοψίζεται στην εξεύρεση όλων των υπογράφων που εμφανίζονται σε τουλάχιστον s γράφους σε ένα σύνολο γράφων (dataset), όπου το s καθορίζεται από το χρήστη. Ο έλεγχος ισομορφισμού των γράφων και ο τεράστιος χώρος αναζήτησης των υποφήφιων μοτίβων των γράφων (graph patterns) κάνουν τη διαδικασία χρονοβόρα ακόμη και για μικρά dataset. Για αυτό το λόγο έχουν γίνει αρκετές δουλειές πάνω σε παράλληλες υλοποιήσεις αυτών των αλγόριθμων σε διάφορες αρχιτεκτονικές.
Στην παρούσα εργασία γίνεται μια προσπάθεια παραλληλοποίησης σε GPU ενός από τους πιο αποδοτικούς αλγόριθμους στο πεδίο του frequent subgraph mining, του gSpan (Graph-Based Substructure Pattern Mining).
