Συντάχθηκε 16-10-2013 09:58
από Eleni Stamataki
Email συντάκτη: estamataki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: σύνταξη/αποχώρηση υπάλληλος.
Σχολή Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΑΘΑΝΑΣΙΟΣ ΣΤΡΑΤΙΚΟΠΟΥΛΟΣ
με θέμα
“Ανάπτυξη αναδιατασσόμενων αρχιτεκτονικών για Εξόρυξη Συχνών Υπογράφων”
Τετάρτη 16 Οκτωβρίου 2013, 14:00
Αίθουσα 2042, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Καθ. Απόστολος Δόλλας (επιβλέπων)
Αν. Καθ. Ιωάννης Παπαευσταθίου
Καθ. Μίνως Γαροφαλάκης
Περίληψη
Τα τελευταία χρόνια η περιοχή του data mining έχει κεντρίσει το ενδιαφέρον της βιομηχανίας και της επιστημονικής κοινότητας, εξαιτίας της ύπαρξης μεγάλου όγκου δεδομένων σε πολλές εφαρμογές και της ανάγκης μετατροπής αυτών των δεδομένων σε χρήσιμη πληροφορία και γνώση.
Μία ειδική περίπτωση του data mining είναι το graph mining. Αντικείμενο αυτού του πεδίου είναι η εξόρυξη χρήσιμης πληροφορίας από δεδομένα, που χρησιμοποιούν ως βασική δομή δεδομένων τους γράφους. Οι γράφοι από τη φύση τους έχουν ιδιότητες, οι οποίες συχνά οδηγούν σε υψηλή αλγοριθμική πολυπλοκότητα. Παρ’ όλα αυτά, έχουν αναπτυχθεί υλοποιήσεις σε γνωστά προβλήματα της περιοχής, όπως είναι η εξόρυξη συχνών μοτίβων (frequent pattern mining), η ομαδοποίηση των δεδομένων (clustering) και η ταξινόμησή τους (classification), οι οποίες καθιστούν τους γράφους ως μία κατάλληλη δομή δεδομένων για την επίλυση γνωστών προβλημάτων της περιοχής του data mining. Σε αυτά τα προβλήματα, η υψηλή πολυπλοκότητα καθώς και η ύπαρξη δεδομένων σε μορφή τεράστιων γράφων, αυξάνει εκθετικά τον χρόνο εκτέλεσης των αλγορίθμων. Για το λόγο αυτό έχουν παρουσιασθεί πολλές παράλληλες υλοποιήσεις, σε hardware και σε software, για πολλούς από τους αλγορίθμους του graph mining.
H παρούσα διπλωματική εργασία είναι η πρώτη στην οποία ένας από τους πιο αποδοτικούς αλγορίθμους στο πεδίο του frequent subgraph mining (gSpan αλγόριθμος) απεικονίζεται σε ένα σύστημα αναδιατασσόμενης λογικής, όπως είναι η FPGA. Επίσης, στην εργασία αυτή αναπτύσσεται μία νέα δομή δεδομένων κατάλληλη για την απεικόνιση και την επεξεργασία ενός γράφου σε αναδιατασσόμενη λογική και γίνεται σύγκριση απέναντι στις άλλες «παραδοσιακές» τεχνικές αναπαράστασης γράφων. Η αρχιτεκτονική, που σχεδιάστηκε πετυχαίνει επιδόσεις, οι οποίες ξεπερνούν τις επιδόσεις της αυθεντικής έκδοσης του αλγορίθμου, κατά μία τάξη μεγέθους. Συνεπώς, αναδεικνύεται η καταλληλόλητα της χρήσης των FPGAs, σε τόσο πολύπλοκα προβλήματα.
Συνημμένα:
-
ΑΝΑΚΟΙΝΩΣΗ ΣΤΡΑΤΙΚΟΠΟΥΛΟΣ.docx
Μεταφορτώσεις: 105,
Μέγεθος: 13 KB application/vnd.openxmlformats-officedocument.wordprocessingml.document
