Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14988
Title: | Graphit-db: Πρότυπο Σύστημα Διαχείρισης Δεδομένων Γράφων |
Authors: | Λεμονιά Μπουλά Σελλής Τιμολέων |
Keywords: | γράφος μονοπάτι ακμή κόμβος pathindex ερώτημα λίστα γειτνίασης αναπαράσταση γράφου αναζήτηση κατά πλάτος αναζήτηση κατά βάθος κοινωνικό δίκτυο |
Issue Date: | 18-Dec-2007 |
Abstract: | Οι γράφοι ως δομή χρησιμοποιούνται από πολύ παλιά για την μοντελοποίηση περίπλοκων δεδομένων. Η πλειοψηφία των γνωστών αλγορίθμων γράφων μπορεί να εφαρμοστεί αποδοτικά είτε σε γράφους με μικρό μέγεθος, είτε σε μη-μεταβαλλόμενους γράφους. Η παρούσα διπλωματική ασχολείται με ερωτήματα πάνω σε δεδομένα που είναι οργανωμένα σε γράφους. Η διαφορά των μεθόδων που θα παρουσιάσουμε στη συνέχεια από τις γνωστές βρίσκεται στον τρόπο αναπαράστασης των γράφων. Οι μέθοδοι που προτείνουμε, χρησιμοποιούν μια αναπαράσταση γράφων, στην οποία κάθε γράφος δίνεται ως σύνολο μονοπατιών. Για την αναπαράσταση αυτή χρησιμοποιούμε μια δομή, την οποία ονομάζουμε PATHINDEX και η οποία περιέχει για κάθε κόμβο στοιχεία, όπως τα μονοπάτια στα οποία εμφανίζεται, η θέση του σ'αυτά και οτιδήποτε άλλο μπορεί να χρειάζεται στον κάθε αλγόριθμο. Υλοποιήσαμε αλγορίθμους που χρησιμοποιούν τη δομή PATHINDEX και συγκρίναμε την απόδοσή τους με γνωστούς από τη βιβλιογραφία αλγορίθμους. Στην περίπτωση των πυκνών γράφων, η πλειοψηφία των μεθόδων που προτείνουμε είναι καλύτερες από τις γνωστές. |
URI: | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14988 |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
DT2007-0233.pdf | 2.96 MB | Adobe PDF | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.