Νέος δυναμικός τύπος γραφημάτων ευρείας κλίμακας και εφαρμογές του
Στην διπλωματική εργασία παρουσιάζεται μια νέα δομή δεδομένων ειδικά σχεδιασμένη για δίκτυα μεταφορών ευρείας κλίμακας τα οποία αλλάζουν δυναμικά. Η νέα δομή δεδομένων γραφημάτων μας παρέχει ταυτόχρονα τρία μοναδικά χαρακτηρισ τικά: 1. Σύμπτυξη(Compactness): ικανότητα να προσπελάσει αποδοτικά διαδο...
Κύριος συγγραφέας: | |
---|---|
Άλλοι συγγραφείς: | |
Μορφή: | Thesis |
Γλώσσα: | Greek |
Έκδοση: |
2013
|
Θέματα: | |
Διαθέσιμο Online: | http://hdl.handle.net/10889/5825 |
id |
nemertes-10889-5825 |
---|---|
record_format |
dspace |
spelling |
nemertes-10889-58252022-09-05T20:32:17Z Νέος δυναμικός τύπος γραφημάτων ευρείας κλίμακας και εφαρμογές του Μιχαήλ, Παναγιώτης Ζαρολιάγκης, Χρήστος Ζαρολιάγκης, Χρήστος Νικολετσέας, Σωτήρης Τσίχλας, Κωνσταντίνος MIchail, Panagiotis Δρομολόγηση Δίκτυα ευρείας κλίμακας Large scale networks 004.015 1 Στην διπλωματική εργασία παρουσιάζεται μια νέα δομή δεδομένων ειδικά σχεδιασμένη για δίκτυα μεταφορών ευρείας κλίμακας τα οποία αλλάζουν δυναμικά. Η νέα δομή δεδομένων γραφημάτων μας παρέχει ταυτόχρονα τρία μοναδικά χαρακτηρισ τικά: 1. Σύμπτυξη(Compactness): ικανότητα να προσπελάσει αποδοτικά διαδοχικές κορυφές και ακμές, μια απαίτηση όλων των αλγορίθμων γραφημάτων). 2. Ευκινησία (Agility): ικανότητα να αλλάξει και να ρυθμίσει εξαρχής την εσωτερική της διάταξη με σκοπό να βελτιώσει την τοπικότητα των αναφορών των στοιχείων, σύμφωνα με έναν δεδομένο αλγόριθμο. 3. Δυναμικότητα (Dynamicity): ικανότητα να ενθέσει ή να διαγράψει αποδοτικά κορυφές και ακμές. Όλες οι προηγούμενες γνωστές δομές γραφημάτων δεν υποστήριζαν τουλάχιστον ένα από τα προηγούμενα χαρακτηριστικά ή/και δεν μπορούσαν να εφαρμοστούν σε δυναμικά δίκτυα μεταφορών ευρείας κλίμακας. Σε αυτή τη διπλωματική εργασία, παρουσιάζεται η πρακτικότητα της νέας δομής γραφημάτων εκτελώντας μια εκτενή πειραματική μελέτη για δρομολόγηση συντομότερων διαδρομών σε Ευρωπαϊκά οδικά δίκτυα ευρείας κλίμακας με μερικές δεκάδες εκατομμύρια κορυφές και ακμές. Χρησιμοποιώντας κλασικούς αλγόριθμους εύρεσης συντομότερων διαδρομών, επιτυγχάνονται εύκολα χρόνοι ερωτημάτων από μια αρχική κορυφή σε μια τελική κορυφή της τάξης των milliseconds, ενώ η νέα δομή γραφημάτων μας μπορεί να ενημερωθεί σε μόλις μερικά microseconds μετά από μια ένθεση ή διαγραφή μιας κορυφής ή ακμής. We present a new graph data structure specifically suited for large scale transportation networks in dynamic scenario. Our graph data structure provides tree unique characteristics, namely compactness, agility and dynamicity. All previous data structures were lacking support in at least one of the aforementioned characteristics. We demonstrate the practicality of the new graph data structure by conducting experiments on large scale European road networks, achieving query times of classical routing algorithms in the order of milliseconds and update times in the order of a few microseconds. 2013-02-01T08:39:28Z 2013-02-01T08:39:28Z 2012-07-09 2013-02-01 Thesis http://hdl.handle.net/10889/5825 gr Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. 0 application/pdf |
institution |
UPatras |
collection |
Nemertes |
language |
Greek |
topic |
Δρομολόγηση Δίκτυα ευρείας κλίμακας Large scale networks 004.015 1 |
spellingShingle |
Δρομολόγηση Δίκτυα ευρείας κλίμακας Large scale networks 004.015 1 Μιχαήλ, Παναγιώτης Νέος δυναμικός τύπος γραφημάτων ευρείας κλίμακας και εφαρμογές του |
description |
Στην διπλωματική εργασία παρουσιάζεται μια νέα δομή δεδομένων ειδικά σχεδιασμένη για δίκτυα μεταφορών ευρείας κλίμακας τα οποία αλλάζουν δυναμικά. Η νέα δομή δεδομένων γραφημάτων μας παρέχει ταυτόχρονα τρία μοναδικά χαρακτηρισ τικά:
1. Σύμπτυξη(Compactness): ικανότητα να προσπελάσει αποδοτικά διαδοχικές κορυφές και ακμές, μια απαίτηση όλων των αλγορίθμων γραφημάτων).
2. Ευκινησία (Agility): ικανότητα να αλλάξει και να ρυθμίσει εξαρχής την εσωτερική της διάταξη με σκοπό να βελτιώσει την τοπικότητα των αναφορών των στοιχείων, σύμφωνα με έναν δεδομένο αλγόριθμο.
3. Δυναμικότητα (Dynamicity): ικανότητα να ενθέσει ή να διαγράψει αποδοτικά κορυφές και ακμές.
Όλες οι προηγούμενες γνωστές δομές γραφημάτων δεν υποστήριζαν τουλάχιστον ένα από τα προηγούμενα χαρακτηριστικά ή/και δεν μπορούσαν να εφαρμοστούν σε δυναμικά δίκτυα μεταφορών ευρείας κλίμακας.
Σε αυτή τη διπλωματική εργασία, παρουσιάζεται η πρακτικότητα της νέας δομής γραφημάτων εκτελώντας μια εκτενή πειραματική μελέτη για δρομολόγηση συντομότερων διαδρομών σε Ευρωπαϊκά οδικά δίκτυα ευρείας κλίμακας με μερικές δεκάδες εκατομμύρια κορυφές και ακμές. Χρησιμοποιώντας κλασικούς αλγόριθμους εύρεσης συντομότερων διαδρομών, επιτυγχάνονται εύκολα χρόνοι ερωτημάτων από μια αρχική κορυφή σε μια τελική κορυφή της τάξης των milliseconds, ενώ η νέα δομή γραφημάτων μας μπορεί να ενημερωθεί σε μόλις μερικά microseconds μετά από μια ένθεση ή διαγραφή μιας κορυφής ή ακμής. |
author2 |
Ζαρολιάγκης, Χρήστος |
author_facet |
Ζαρολιάγκης, Χρήστος Μιχαήλ, Παναγιώτης |
format |
Thesis |
author |
Μιχαήλ, Παναγιώτης |
author_sort |
Μιχαήλ, Παναγιώτης |
title |
Νέος δυναμικός τύπος γραφημάτων ευρείας κλίμακας και εφαρμογές του |
title_short |
Νέος δυναμικός τύπος γραφημάτων ευρείας κλίμακας και εφαρμογές του |
title_full |
Νέος δυναμικός τύπος γραφημάτων ευρείας κλίμακας και εφαρμογές του |
title_fullStr |
Νέος δυναμικός τύπος γραφημάτων ευρείας κλίμακας και εφαρμογές του |
title_full_unstemmed |
Νέος δυναμικός τύπος γραφημάτων ευρείας κλίμακας και εφαρμογές του |
title_sort |
νέος δυναμικός τύπος γραφημάτων ευρείας κλίμακας και εφαρμογές του |
publishDate |
2013 |
url |
http://hdl.handle.net/10889/5825 |
work_keys_str_mv |
AT michaēlpanagiōtēs neosdynamikostyposgraphēmatōneureiasklimakaskaiepharmogestou |
_version_ |
1771297281841037312 |