National and Kapodistrian University of Athens
Αποδοτικοί Υπολογισμοί σε Μονοπάτια Γράφων
Abstract
dc:descriptionΣτην παρούσα εργασία ασχολούμαστε με υπολογισμούς σε γράφους βασισμένοι στην άλγεβρα μονοπατιών. Στόχος μας είναι η απάντηση, σε πραγματικό χρόνο, επερωτήσεων για τον υπολογισμό ιδιοτήτων μεταξύ διατεταγμένων ζευγών κόμβων βασιζόμενοι στις ιδιότητες των ακμών των μονοπατιών που τους συνδέουν, ενόσω ο υποκείμενος γράφος αλλάζει δυναμικά, με προσθήκη νέων ακμών και αλλαγή των ιδιοτήτων των υπαρχόντων. Μέσω αυτής της γενικής μορφής υπολογισμών στόχος μας είναι η δημιουργία ενός συστήματος προσωποποίησης και συστάσεων γενικού σκοπού. Το συγκεκριμένο πεδίο εφαρμογής μας επιτρέπει να αξιοποιήσουμε σημαντικές παρατηρήσεις (μικρό μέρος του συνολικού γράφου ενεργό ανά πάσα στιγμή, τοπικότητα των στόχων των επερωτήσεων), ώστε να αυξήσουμε την απόδοση του προτεινόμενου συστήματος, καθώς και να αναπτύξουμε παράλληλες τεχνικές για τη μαζική εκτέλεση των απαιτούμενων υπολογισμών πάνω από κατανεμημένα υπολογιστικά συστήματα. Αν και οι τεχνικές που αναπτύξαμε δεν κάνουν κάποια παραδοχή για το είδος των υπολογισμών που θέλουμε να εφαρμόσουμε στο γράφο, δείχνουμε ότι αν έχουν ένα σύνολο συγκεκριμένων ιδιοτήτων (επιμεριστική και προσεταιριστική ιδιότητα), τότε το πρόβλημα μπορεί να διατυπωθεί ως μια επέκταση του μεταβατικού εγκλεισμού σε κατευθυνόμενους γράφους, αυξάνοντας με αυτόν τον τρόπο κατακόρυφα την απόδοση του συστήματος. Τέλος, παραθέτουμε τεχνικές που διατηρούν προϋπολογισμένα τμήματα των υπολογισμών, με στόχο την περαιτέρω βελτίωση του χρόνου απάντησης των επερωτήσεων.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Καρβούνης Εμμανουήλ
Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1316312