Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)

Permanent URI for this collection

https://hdl.handle.net/10889/24

Browse

Now showing 1 - 20 of 147

Open Access
Βασικές δομές δεδομένων και η εφαρμογή τους στην υπολογιστική γεωμετρία και στην ανάκτηση πληροφορίας
(1997-07-07) Μακρής, Χρήστος; Makris, Christos
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Το πρόβλημα της δόμησης δεδομένων συνίσταται στην επιλογή της συγκεκριμένης υλοποίησης ενός αφηρημένου τύπου δεδομένων για την αποτελεσματική αντιμετώπιση αλγοριθμικών προβλημάτων. Ένας αφηρημένος τύπος δεδομένων συνίσταται στον ορισμό ενός συνόλου αντικειμένων και των επιτρεπόμενων λειτουργιών που μπορούν να εφαρμοστούν σε αυτό. Η συγκεκριμένη εργασία αποτελεί μια μελέτη των βασικών δομών δεδομένων στην επιστήμη των υπολογιστών και της εφαρμογής τους στην ανάπτυξη αποτελεσματικών αλγορίθμων για προβλήματα στην κύρια μνήμη (περιοχή της Υπολογιστικής Γεωμετρίας) και στη δευτερεύουσα μνήμη (περιοχή Ανάκτησης Πληροφορίας). Στην περιοχή της υπολογιστικής γεωμετρίας, ασχολείται με προβλήματα τομών για απλά και γενικευμένα αντικείμενα, με το πρόβλημα της διαπέρασης ορθογωνίων και με το πρόβλημα της κυριαρχίας σημείων. Στην περιοχή της Ανάκτησης Πληροφορίας, ασχολείται με την ανάπτυξη μιας νέας δομής δεδομένων για την αποτελεσματική αποθήκευση και ανάκτηση αρχείων υπογραφών. Οι προτεινόμενοι αλγόριθμοι αναλύονται κυρίως θεωρητικά, με εξαίρεση τη μέθοδο αποθήκευσης αρχείων υπογραφών, όπου παρουσιάζονται επίσης πειραματικά αποτελέσματα.
Open Access
Μέθοδοι απόκρυψης πληροφορίας και υδατογράφηση ως τεχνικές προστασίας πνευματικών δικαιωμάτων και πιστοποίησης της αυθεντικότητας
(2007-06-22T12:03:17Z) Αρμένη, Σπυριδούλα; Χριστοδουλάκης, Δημήτριος; Στουραΐτης, Αθανάσιος; Παυλίδης, Γεώργιος; Γαροφαλάκης, Ιωάννης; Σταματίου, Ιωάννης; Μπερμπερίδης, Κωνσταντίνος; Ξένος, Μιχάλης; Χριστοδουλάκης, Δημήτριος; Armeni, Spyridoula
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Η προστασία των πνευματικών δικαιωμάτων και η απόδειξη γνησιότητας του κατόχου, επομένως και η πιστοποίηση της αυθεντικότητας των ψηφιακών αντικειμένων είναι ένα πολύ καυτό ζήτημα και για την επίλυσή του επιστρατεύονται μέθοδοι απόκρυψης πληροφορίας και τεχνικές υδατογράφησης. Εκτός από τη φιλοσοφική αντιμετώπιση του θέματος, προτείνονται μια μέθοδος απόκρυψης πληροφορίας και δύο τεχνικές υδατογράφησης, με σκοπό την προστασία των πνευματικών δικαιωμάτων και την πιστοποίηση της αυθεντικότητας των ψηφιακών αντικειμένων. Η μέθοδος απόκρυψης πληροφορίας δανείζεται έννοιες από την κρυπτογραφία εισάγοντας σε μεγάλες εικόνες ένα δύσκολο στιγμιότυπο, δηλαδή έναν τρία χρωματίσιμο γράφο. Ο γράφος μαζί με το χρωματισμό του αποτελεί το κλειδί. Για να μην αποκαλυφθεί όλος ο χρωματισμός του γράφου σε μια πιθανή διαμάχη, εφαρμόζεται το πρωτόκολλο των διαντιδραστικών αποδείξεων μηδενικής γνώσης (ZKIP) για δύσκολα υπολογιστικά προβλήματα. Η διαδικασία της ένθεσης γίνεται με χρήση του μετασχηματισμού wavelets, παρέχοντας καλή ποιότητα των παραγόμενων εικόνων και ανθεκτικότητα σε περιπτώσεις επιθέσεων. Οι δύο τεχνικές υδατογράφησης εφαρμόζονται στο χωρικό πεδίο και στο πεδίο συχνοτήτων, αντίστοιχα. Η τεχνική που εφαρμόστηκε στο χωρικό πεδίο εκμεταλλεύεται τυχόν ομοιότητες του υδατογραφήματος με τις αρχικές εικόνες για να επιλεγούν οι θέσεις ένθεσης. Αντίθετα στην τεχνική υδατογράφησης που εφαρμόστηκε στο πεδίο συχνοτήτων γίνεται χρήση του μετασχηματισμού wavelet. Σε όλες τις τεχνικές παρατηρήθηκαν ικανοποιητικά αποτελέσματα μετά την ένθεση της εισαγόμενης πληροφορίας έτσι ώστε να μη είναι οπτικά αντιληπτή. Επίσης εξετάστηκε και η ανθεκτικότητα της εισαγόμενης πληροφορίας στις εικόνες ύστερα από πιθανές επιθέσεις και επιβεβαιώθηκε ότι επιζεί ένα αρκετά μεγάλο ποσοστό της εισαγόμενης πληροφορίας, γεγονός που καταξιώνει τις προτεινόμενες μεθόδους.
Open Access
Μεθοδολογία έγκαιρης εκτίμησης της γνώμης των χρηστών για την ποιότητα λογισμικού
(2007-06-25T06:08:15Z) Σταυρινούδης, Δημήτριος; Χριστοδουλάκης, Δημήτριος; Γαροφαλάκης, Γιάννης; Τσακαλίδης, Θανάσης; Ξένος, Μιχάλης; Αβούρης, Νίκος; Πιντέλας, Παναγιώτης; Σπυράκης, Παύλος; Χριστοδουλάκης, Δημήτριος; Stavrinoudis, Dimitris
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Στην παρούσα διδακτορική διατριβή προτείνονται διάφορες μέθοδοι και τεχνικές που συνεισφέρουν στην έγκαιρη εκτίμηση της γνώμης των χρηστών για την ποιότητα λογισμικού. Τέτοιες μέθοδοι είναι α) η επιλογή και χρήση μετρικών λογισμικού και η ανάλυση των αποτελεσμάτων τους, β) η δόμηση και η ανάλυση ερωτηματολογίων για τη μέτρηση της γνώμης των χρηστών για την ποιότητα λογισμικού, γ) η συσχέτιση εσωτερικών μετρικών λογισμικού με τα εξωτερικά ποιοτικά χαρακτηριστικά ενός προγράμματος λογισμικού, δ) η μεταβολή της γνώμης του χρήστη για την ποιότητα ενός προγράμματος λογισμικού με την πάροδο του χρόνου σε σχέση με το επίπεδο εμπειρίας του χρήστη και ε) η χρήση και η προσαρμογή κανόνων και μοντέλων από τη θεωρία Αναθεώρησης Άποψης. Όλες οι παραπάνω μέθοδοι συνδυάζονται ώστε να συνεισφέρουν στην προτεινόμενη μεθοδολογία της διδακτορικής διατριβής.
Open Access
Η χρήση σημασιολογικών δικτύων για τη διαχείριση του περιεχομένου του παγκόσμιου ιστού
(2007-06-25T06:08:24Z) Στάμου, Σοφία; Χριστοδουλάκης, Δημήτρης; Σκόδρας, Αθανάσιος; Ιορδανίδου, Άννα; Σγάρμπας, Κυριάκος; Φακωτάκης, Νικόλαος; Πιντέλας, Παναγιώτης; Μπούρας, Χρήστος; Χριστοδουλάκης, Δημήτρης; Stamou, Sofia
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Η παρούσα διατριβή πραγματεύεται την ενσωμάτωση ενός σημασιολογικού δικτύου λημμάτων σ’ ένα σύνολο εφαρμογών Διαδικτύου για την αποτελεσματική διαχείριση του περιεχομένου του Παγκόσμιου Ιστού. Τα δίκτυα σημασιολογικά συσχετισμένων λημμάτων αποτελούν ένα είδος ηλεκτρονικών λεξικών στα οποία καταγράφεται σημασιολογική πληροφορία για τα λήμματα που περιλαμβάνουν, όπου τα τελευταία αποθηκεύονται σε μια δενδρική δομή δεδομένων. Ο τρόπος δόμησης του περιεχομένου των σημασιολογικών δικτύων παρουσιάζει αρκετές ομοιότητες με την οργάνωση που ακολουθούν οι ιστοσελίδες στον Παγκόσμιο Ιστό, με αποτέλεσμα τα σημασιολογικά δίκτυα να αποτελούν έναν σημασιολογικό πόρο άμεσα αξιοποιήσιμο από ένα πλήθος εφαρμογών Διαδικτύου που καλούνται να διαχειριστούν αποδοτικά το πλήθος των δεδομένων που διακινούνται στον Παγκόσμιο Ιστό. Μετά από επισκόπηση των τεχνικών που παρουσιάζονται στη διεθνή βιβλιογραφία για τη διαχείριση του περιεχομένου του Παγκόσμιου Ιστού, προτείνεται και υλοποιείται ένα πρότυπο μοντέλο διαχείρισης ιστοσελίδων, το οποίο κάνοντας εκτεταμένη χρήση ενός εμπλουτισμένου σημασιολογικού δικτύου λημμάτων, εντοπίζει εννοιολογικές ομοιότητες μεταξύ του περιεχομένου διαφορετικών ιστοσελίδων και με βάση αυτές επιχειρεί και κατορθώνει την αυτοματοποιημένη και αποδοτική δεικτοδότηση, κατηγοριοποίηση και ταξινόμηση του πλήθους των δεδομένων του Παγκόσμιου Ιστού. Για την επίδειξη του μοντέλου διαχείρισης ιστοσελίδων που παρουσιάζεται, υιοθετούμε το μοντέλο πλοήγησης στους θεματικούς καταλόγους του Παγκόσμιου Ιστού και καταδεικνύουμε πειραματικά τη συμβολή των σημασιολογικών δικτύων σε όλα τα στάδια της δημιουργίας θεματικών καταλόγων Διαδικτύου. Συγκεκριμένα, εξετάζεται η συνεισφορά των σημασιολογικών δικτύων: (i) στον ορισμό και εμπλουτισμό των θεματικών κατηγοριών των καταλόγων του Παγκόσμιου Ιστού, (ii) στην επεξεργασία και αποσαφήνιση του περιεχομένου των ιστοσελίδων, (iii) στον αυτόματο εμπλουτισμό των θεματικών κατηγοριών ενός δικτυακού καταλόγου, (iv) στην ταξινόμηση των ιστοσελίδων που έχουν δεικτοδοτηθεί στις αντίστοιχες θεματικές κατηγορίες ενός καταλόγου, (v) στη διαχείριση των περιεχομένων των θεματικών καταλόγων με τρόπο που να διασφαλίζει την παροχή χρήσιμων ιστοσελίδων προς τους χρήστες, και τέλος (vi) στην αναζήτηση πληροφορίας στους θεματικούς καταλόγους του Παγκόσμιου Ιστού. Η επιτυχία του προτεινόμενου μοντέλου επιβεβαιώνεται από τα αποτελέσματα ενός συνόλου πειραματικών εφαρμογών που διενεργήθηκαν στο πλαίσιο της παρούσας διατριβής, όπου καταδεικνύεται η συμβολή των σημασιολογικών δικτύων στην αποτελεσματική διαχείριση των πολυάριθμων και δυναμικά μεταβαλλόμενων ιστοσελίδων του Παγκόσμιου Ιστού. Η σπουδαιότητα του προτεινόμενου μοντέλου διαχείρισης ιστοσελίδων, έγκειται στο ότι, εκτός από αυτόνομο εργαλείο διαχείρισης και οργάνωσης ιστοσελίδων, συνιστά το πρώτο επίπεδο επεξεργασίας σε ευρύτερο πεδίο εφαρμογών, όπως είναι η εξαγωγή περιλήψεων, η εξόρυξη πληροφορίας, η θεματικά προσανατολισμένη προσκομιδή ιστοσελίδων, ο υπολογισμός του ρυθμού μεταβολής των δεδομένων του Παγκόσμιου Ιστού, η ανίχνευση ιστοσελίδων με παραποιημένο περιεχόμενο, κτλ.
Open Access
Αποδοτικές τεχνικές αντιστοίχισης και ψηφιακής υδατογράφησης εικόνων
(2007-06-25T06:08:33Z) Καρύμπαλη, Ειρήνη; Μπερμπερίδης, Κωνσταντίνος; Εμμανουήλ Ψαράκης; Σκόδρας, Αθανάσιος; Στουραΐτης, Αθανάσιος; Φωτόπουλος, Σπυρίδων; Παπαθεοδώρου, Θεόδωρος; Λυκοθανάσης, Σπυρίδων; Μπερμπερίδης, Κωνσταντίνος; Karybali, Irene
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Η αντιστοίχιση εικόνων έχει σαν σκοπό την εύρεση γεωμετρικών και άλλων διαφορών ανάμεσα σε δύο ή περισσότερες εικόνες. Η ψηφιακή υδατογράφηση εικόνων προσφέρει κατοχύρωση των πνευματικών δικαιωμάτων, εισάγοντας στις εικόνες ένα αδιόρατο σήμα, ένα υδατογράφημα, με τέτοιο τρόπο ώστε να είναι δύσκολο να αφαιρεθεί. Η αντιστοίχιση μπορεί να αποτελέσει τμήμα της ψηφιακής υδατογράφησης, στη φάση της ανίχνευσης του υδατογραφήματος. Επιπλέον, για την ανίχνευση του υδατογραφήματος χρησιμοποιούνται παρόμοιες ή και ίδιες μετρικές ομοιότητας με αυτές που χρησιμοποιούνται στην αντιστοίχιση. Έτσι, οποιαδήποτε βελτίωση αφορά την αντιστοίχιση ή τις μετρικές ομοιότητας μπορεί να έχει θετικές επιδράσεις και στην ψηφιακή υδατογράφηση. Η έρευνα που έγινε στα πλαίσια της διδακτορικής διατριβής σε σχέση με το πρόβλημα της αντιστοίχισης αφορά τη συσχέτιση των εικόνων στο χωρικό πεδίο, η οποία έχει το εξής μειονέκτημα: η περιοχή γύρω από τη μέγιστη τιμή της μπορεί να έχει μεγάλο εύρος και να επηρεάζει την ακρίβεια της αντιστοίχισης. Για την αντιμετώπιση αυτού του προβλήματος, προτείνεται μια διαδικασία προ-λεύκανσης των εικόνων, βασισμένη στο φίλτρο σφάλματος πρόβλεψης. Επίσης, αναπτύσσεται ένας επαναληπτικός αλγόριθμος αντιστοίχισης για μετατοπίσεις και περιστροφές, ο οποίος εφαρμόζεται σε ακολουθίες ιατρικών εικόνων με σκοπό τη διάγνωση δυσπλασιών και κακοηθειών. Ένα δεύτερο μειονέκτημα της χωρικής συσχέτισης είναι το μεγάλο υπολογιστικό της κόστος. Στη διδακτορική διατριβή προτείνεται ένα γρήγορο σχήμα υπολογισμού της, το οποίο βασίζεται σε κατάλληλη τμηματοποίηση της εικόνας και στη χρήση του μετασχηματισμού Fourier. Επίσης, το πιο απαιτητικό κομμάτι της διαδικασίας αντιστοίχισης είναι ο υπολογισμός της χρησιμοποιούμενης μετρικής σαν συνάρτηση της σχετικής θέσης των εικόνων. Έτσι, αναπτύσσεται ένας αποδοτικός επαναληπτικός αλγόριθμος, ο οποίος μειώνει σημαντικά τις αναζητήσεις που απαιτούνται για την εύρεση του μεγίστου του συντελεστή συσχέτισης και παρέχει ακρίβεια εικονοστοιχείου. Τέλος, προτείνεται μια τεχνική η οποία παρέχει ακρίβεια υποδιαίρεσης εικονοστοιχείου και βασίζεται στη μεγιστοποίηση του συντελεστή συσχέτισης. Η τεχνική αυτή δεν απαιτεί ανακατασκευή των τιμών της έντασης και παρέχει μια λύση κλειστού τύπου για την εκτίμηση της μετατόπισης. Όσο αφορά το πρόβλημα της υδατογράφησης, η έρευνα που έγινε στα πλαίσια της διδακτορικής διατριβής στοχεύει στην ένθεση ισχυρών υδατογραφημάτων στο χωρικό πεδίο και στη βελτίωση της ανίχνευσής τους. Καταρχήν, προτείνεται μια χωρική αντιληπτική μάσκα, η οποία βασίζεται στην τοπική διασπορά του σφάλματος πρόβλεψης της αρχικής εικόνας. Παράλληλα, αναπτύσσεται ένα «τυφλό» σύστημα ανίχνευσης και η βελτιωμένη απόδοσή του σε σχέση με υπάρχοντες ανιχνευτές αποδεικνύεται θεωρητικά για τη γενική περίπτωση επίθεσης με γραμμικό φίλτρο και θόρυβο. Στη συνέχεια, παράγεται μια νέα χωρική μάσκα η οποία επιτρέπει την ένθεση υδατογραφημάτων με εξαιρετικά μεγάλη ενέργεια, διατηρώντας ταυτόχρονα την ποιότητα της εικόνας σε πολύ καλό επίπεδο. Η απόδοσή της συγκρίνεται με πολύ γνωστές και ευρέως χρησιμοποιούμενες μάσκες και αποδεικνύεται σημαντικά καλύτερη. Επίσης, αναπτύσσεται ένα βελτιωμένο σχήμα ανίχνευσης, το οποίο σε συνδυασμό με την προτεινόμενη μάσκα έχει πολύ καλή απόδοση. Τέλος, προτείνεται μια μέθοδος εισαγωγής υδατογραφήματος στην εικόνα με πολλαπλασιαστικό τρόπο, χρησιμοποιώντας χωρο-χρονική κωδικοποίηση μπλοκ και ειδικότερα μια 4x4 πραγματική, ορθογώνια διάταξη συμβόλων. Το σχήμα αυτό αποδεικνύεται να έχει πολύ καλύτερη απόδοση σε σχέση με την επαναληπτική υδατογράφηση.
Open Access
Αποδοτικοί αλγόριθμοι και προσαρμοστικές τεχνικές διαχείρισης δικτυακών πληροφοριακών συστημάτων και εφαρμογών παγκόσμιου ιστού
(2007-06-25T06:08:43Z) Σακκόπουλος, Ευάγγελος; Τσακαλίδης, Αθανάσιος; Παυλίδης, Γεώργιος; Γαροφαλάκης, Ιωάννης; Χατζηλυγερούδης, Ιωάννης; Πιντέλας, Παναγιώτης; Λυκοθανάσης, Σπυρίδων; Μακρής, Χρήστος; Τσακαλίδης, Αθανάσιος; Sakkopoulos, Evangelos
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Στα πλαίσια της διδακτορικής μας διατριβής ασχοληθήκαμε με προβλήματα διαχείρισης δικτυακών πληροφοριακών συστημάτων που βασίζονται σε τεχνολογίες παγκόσμιου ιστού (network-centric information systems, netcentric information systems, web information systems). Η έννοια της δικτυο-κεντρικής προσέγγισης (netcentric) προσπαθεί να αποδώσει την τάση να χρησιμοποιείται η δικτυακή υποδομή και τεχνολογία όλο και περισσότερο στα πληροφοριακά συστήματα και τις εφαρμογές παγκόσμιου ιστού για να παρέχουν, να δημοσιοποιούν, να διαμοιράζουν και να επικοινωνούν online υπηρεσίες και πληροφορίες. Κύριος στόχος της διατριβής είναι α) η διασφάλιση της ποιότητας κατά την εξυπηρέτηση, β) η μείωση του χρόνου εντοπισμού και γ) η εξατομίκευση υπηρεσιών και πληροφοριών σε δικτυακά πληροφοριακά περιβάλλοντα και εφαρμογές που βασίζονται σε τεχνολογίες μηχανικής Παγκόσμιου Ιστού. Σε πρώτο επίπεδο, οι αποδοτικοί αλγόριθμοι που αναπτύξαμε αφορούν τις υπηρεσίες Web Services που έχουν σχεδιαστεί να υποστηρίζουν διαλειτουργική αλληλεπίδραση μεταξύ μηχανών με χρήση δικτυακής υποδομής. Πρόκειται ένα τεχνολογικό πλαίσιο το οποίο προτυποποιήθηκε από το W3 Consortium (http://www.w3.org) και γνωρίζει την ευρεία υποστήριξη τόσο της επιστημονικής κοινότητας τεχνολογιών πληροφορικής και επικοινωνιών όσο και των επαγγελματιών μηχανικών Η/Υ και της βιομηχανίας πληροφορικής παγκοσμίως. Αναλυτικότερα στο πρώτο μέρος της διατριβής δίνουμε αρχικά μία νέα κατηγοριοποίηση και συγκριτική παρουσίαση των λύσεων και προβλημάτων που αφορούν αποδοτικές λύσεις αλγορίθμων διαχείρισης και αναζήτησης υπηρεσιών. Στη συνέχεια, εισάγουμε μια σειρά από νέους αποδοτικούς αλγορίθμους διαχείρισης και αναζήτησης υπηρεσιών που διασφαλίζουν την ποιότητα της παρεχόμενης υπηρεσίας και βελτιώνουν την πολυπλοκότητα στο χρόνο εντοπισμού μιας υπηρεσίας. Συνολικά στο πρώτο μέρος παρουσιάζουμε: - Αποδοτικούς αλγορίθμους δυναμικής επιλογής Web Service που λαμβάνουν υπόψη μη λειτουργικές προδιαγραφές για ποιότητα και απόδοση κατά την προσπάθεια χρήσης (consumption) του Web Service (QoWS enabled WS discovery). - Αποδοτικούς αλγορίθμους διαχείρισης και αναζήτησης υπηρεσιών δικτυο-κεντρικών πληροφοριακών συστημάτων οι οποίοι βασίζονται σε αποκεντρικοποιημένες δικτυακές λύσεις ειδικά σχεδιασμένες για WS καταλογογράφηση (decentralized WS discovery). Σε δεύτερο επίπεδο, δίνουμε αποδοτικές προσαρμοστικές μεθόδους για την εξατομίκευση των αποτελεσμάτων αναζήτησης πληροφοριών στον Παγκόσμιο Ιστό. Με τον τρόπο αυτό επιτυγχάνουμε βελτίωση της απόδοσης τόσο για τις εσωτερικές λειτουργίες διαχείρισης και αναζήτησης των δικτυακών πληροφοριακών συστημάτων όσο και του τελικού αποτελέσματος, της πληροφορίας δηλαδή, που παρουσιάζουν τα συστήματα αυτά στον τελικό χρήστη. Συγκεκριμένα, στο δεύτερο μέρος της διατριβής εισάγουμε μια σειρά από τρεις αλγορίθμους εξατομίκευση των αποτελεσμάτων αναζήτησης, οι οποίοι βασίζονται σε τεχνικές μετρικών συνδέσμων (link metrics). Το κύριο πλεονέκτημα των τεχνικών που προτείνουμε είναι ότι επιτρέπουν, με τη χρήση μιας αρκετά απλής μεθοδολογίας, την εξατομίκευση των αποτελεσμάτων αναζήτησης, χωρίς να επιβαρύνονται οι χρήστες σε όγκο αποθήκευσης ή με καθυστερήσεις λόγου χρόνου εκτέλεσής τους. Επιτυγχάνουμε εξατομικευμένη αναζήτηση εφαρμόζοντας τεχνικές ανάλυσης και επεξεργασίας συνδέσμων όχι στο γράφο ιστού αλλά για πρώτη φορά σε αρκετά μικρότερους εξατομικευμένους γράφους που σχηματίζονται από διαθέσιμες σημασιολογικές ταξονομίες. Συνοψίζοντας τα ερευνητικά αποτελέσματα του δεύτερου μέρους παρουσιάζουμε τα ακόλουθα: - Αποδοτικοί αλγόριθμοι για εξατομικευμένη αναζήτηση πληροφορίας (personalized searching) στον Παγκόσμιο Ιστό. - Μηχανισμός προσαρμοστικής παρουσίασης αποτελεσμάτων αναζήτησης με χρήση πολλαπλών επιπέδων κατηγοριοποίησης. - Επέκταση των αλγορίθμων για μηχανισμούς στοχευμένης συλλογής σελίδων (focused web crawlers) που αποτελούν εναλλακτική της εξατομικευμένης αναζήτησης πληροφοριών. Τέλος στο τρίτο και τελευταίο μέρος της διατριβής παρουσιάζουμε μια σειρά από εφαρμογές, αρχιτεκτονικές και λειτουργικά πλαίσια τα οποία αφορούν δικτυακά πληροφοριακά περιβάλλοντα στα οποία εφαρμόζουμε τεχνικές διαχείρισης υπηρεσιών και μηχανισμούς εξατομίκευσης πληροφοριών. O κύριος στόχος της παρουσίασης των λύσεων αυτών είναι να επιδειχθεί ότι οι προτεινόμενοι αποδοτικοί αλγόριθμοι, που παρουσιάστηκαν στα προηγούμενα κεφάλαια, έχουν εφαρμογή σε πολλαπλά προβλήματα διαφορετικών επιστημονικών και τεχνολογικών πεδίων που χρησιμοποιούν δικτυακά πληροφοριακά συστήματα και εφαρμογές παγκόσμιου ιστού.
Open Access
Αποδοτικοί αλγόριθμοι εξατομίκευσης βασισμένοι σε εξόρυξη γνώσης απο δεδομένα χρήσης Web
(2007-06-25T06:12:31Z) Ρήγκου, Μαρία; Τσακαλίδης, Αθανάσιος; Παυλίδης, Γεώργιος; Γαροφαλάκης, Γιάννης; Χατζηλυγερούδης, Ιωάννης; Σπυράκης, Παύλος; Λυκοθανάσης, Σπυρίδων; Μακρής, Χρήστος; Μπερμπερίδης, Κωνσταντίνος; Rigou, Maria
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Το Web αποτελεί πλέον µια τεράστια αποθήκη πληροφοριών και συνεχίζει να µεγαλώνει εκθετικά, ενώ η ανθρώπινη ικανότητα να εντοπίζει, να επεξεργάζεται και να αντιλαµβάνεται τις πληροφορίες παραµένει πεπερασµένη. Το πρόβληµα στις µέρες µας δεν είναι η πρόσβαση στην πληροφορία, αλλά το ότι όλο και περισσότεροι άνθρωποι µε διαφορετικές ανάγκες και προτιµήσεις πλοηγούνται µέσα σε περίπλοκες δοµές Web χάνοντας στην πορεία το στόχο της αναζήτησής τους. Η εξατοµίκευση, µια πολυσυλλεκτική ερευνητική περιοχή, αποτελεί µια από τις πιο πολλά υποσχόµενες προσεγγίσεις για τη λύση του προβλήµατος του πληροφοριακού υπερφόρτου, παρέχοντας κατάλληλα προσαρµοσµένες εµπειρίες πλοήγησης. Η διατριβή εξετάζει αλγοριθµικά θέµατα που σχετίζονται µε την υλοποίηση αποδοτικών σχηµάτων εξατοµίκευσης σε περιβάλλον web, βασισµένων σε εξόρυξη γνώσης από δεδοµένα χρήσης web. Οι τεχνικές ανακάλυψης προτύπων που µελετώνται περιλαµβάνουν το clustering, την εξόρυξη κανόνων συσχέτισης και την ανακάλυψη σειριακών προτύπων, ενώ οι προτεινόµενες λύσεις εξατοµίκευσης που βασίζονται στις δύο τελευταίες τεχνικές συνδυάζουν τα δεδοµένα χρήσης µε δεδοµένα περιεχοµένου και δοµής. Ειδικότερα, στο πρώτο κεφάλαιο της διατριβής, ορίζεται το επιστηµονικό πεδίο των σύγχρονων τεχνολογιών εξατοµίκευσης στο περιβάλλον του web, εστιάζοντας στη στενή σχέση τους µε το χώρο του web mining, στοιχειοθετώντας µε αυτό τον τρόπο το γενικότερο πλαίσιο αναφοράς. Στη συνέχεια, περιγράφονται τα διαδοχικά στάδια της τυπικής διαδικασίας εξατοµίκευσης µε έµφαση στη φάση ανακάλυψης προτύπων και τις τεχνικές machine learning που χρησιµοποιούνται σε δεδοµένα χρήσης web και το κεφάλαιο ολοκληρώνεται µε µια συνοπτική περιγραφή της συµβολής της διατριβής στο πεδίο της εξατοµίκευσης σε περιβάλλον web. Στο δεύτερο κεφάλαιο προτείνεται ένας αλγόριθµος για εξατοµικευµένο clustering, που βασίζεται σε µια δοµή range tree που διατρέχεται σε πρώτη φάση για τον εντοπισµό των web αντικειµένων που ικανοποιούν τα ατοµικά κριτήρια του χρήστη. Στα αντικείµενα αυτά, εφαρµόζεται στη συνέχεια clustering, ώστε να είναι δυνατή η αποδοτικότερη διαχείρισή τους και να διευκολυνθεί η διαδικασία λήψης αποφάσεων από πλευράς χρήστη. O αλγόριθµος που προτείνεται αποτελεί βελτίωση του αλγόριθµου kmeans range, καθώς εκµεταλλεύεται το range tree που έχει ήδη κατασκευαστεί κατά το βήµα της εξατοµίκευσης και το χρησιµοποιεί ως τη βασική δοµή πάνω στην οποία στηρίζεται το βήµα του clustering χρησιµοποιώντας εναλλακτικά του k-means, τον αλγόριθµο k-windows. Ο συνολικός αριθµός παραµέτρων που χρησιµοποιούνται για την µοντελοποίηση των αντικειµένων υπαγορεύει και τον αριθµό των διαστάσεων του χώρου εργασίας. Η συνολική πολυπλοκότητα χρόνου του αλγορίθµου είναι ίση µε O(logd-2n+v), όπου n είναι ο συνολικός αριθµός των στοιχείων που δίνονται σαν είσοδος και v είναι το µέγεθος της απάντησης. Στο τρίτο κεφάλαιο της διατριβής προτείνεται ένα αποδοτικό σχήµα πρόβλεψης µελλοντικών δικτυακών αιτήσεων βασισµένο στην εξόρυξη σειριακών προτύπων πλοήγησης (navigation patterns) από αρχεία server log, σε συνδυασµό µε την τοπολογία των συνδέσµων του website και τη θεµατική κατηγοριοποίηση των σελίδων του. Τα µονοπάτια που ακολουθούν οι χρήστες κατά την πλοήγηση καταγράφονται, συµπληρώνονται µε τα κοµµάτια που λείπουν λόγω caching και διασπώνται σε συνόδους και σε επεισόδια, ώστε να προκύψουν σηµασιολογικά πλήρη υποσύνολά τους. Τα πρότυπα που εντοπίζονται στα επεισόδια µοντελοποιούνται µε τη µορφή n-grams και οι αποφάσεις πρόβλεψης βασίζονται στη λογική ενός µοντέλου n-gram+ που προσοµοιάζει το all Kth-τάξης µοντέλο Markov και πιο συγκεκριµένα, το επιλεκτικό µοντέλο Markov. Η υβριδική προσέγγιση που υιοθετεί το προτεινόµενο σχήµα, επιτυγχάνει 100% coverage, ενώ κατά τις πειραµατικές µετρήσεις το άνω όριο της ακρίβειας έφθασε το 71,67% στο σύνολο των προβλέψεων που επιχειρήθηκαν. Το χαρακτηριστικό του πλήρους coverage καθιστά το σχήµα κατάλληλο για συστήµατα παραγωγής συστάσεων, ενώ η ακρίβεια µπορεί να βελτιωθεί περαιτέρω αν µεγαλώσει το παράθυρο πρόβλεψης. Στο τέταρτο κεφάλαιο της διατριβής, εξετάζεται η ενσωµάτωση λειτουργιών εξατοµίκευσης στις ηλεκτρονικές µαθησιακές κοινότητες και προτείνεται ένα σύνολο από δυνατότητες εξατοµίκευσης που διαφοροποιούνται ως προς τα δεδοµένα στα οποία βασίζονται, την τεχνική εξόρυξης προτύπων που χρησιµοποιούν και την αντίστοιχη πολυπλοκότητα υλοποίησης. Οι υπηρεσίες αυτές περιλαµβάνουν: (α) εξατοµίκευση µε βάση το ρόλο του χρήστη, (β) εξατοµίκευση µε βάση το βαθµό δραστηριοποίησης του χρήστη, (γ) εξατοµίκευση µε βάση την ανακάλυψη προτύπων στα ατοµικά ιστορικά µελέτης των εκπαιδευόµενων και (δ) εξατοµίκευση µε βάση συσχετίσεις του περιεχοµένου των µαθηµάτων.
Open Access
Βελτίωση απόδοσης και αποτελεσματικές σχεδιαστικές λύσεις για εφαρμογές Παγκόσμιου Ιστού
(2007-06-25T06:13:25Z) Τζήμας, Γιάννης; Τσακαλίδης, Αθανάσιος; Παυλίδης, Γεώργιος; Γαροφαλάκης, Γιάννης; Χατζηλυγερούδης, Ιωάννης; Σπυράκης, Παύλος; Λυκοθανάσης, Σπυρίδων; Μακρής, Χρήστος; Τσακαλίδης, Αθανάσιος; Tzimas, Giannis
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Η εκθετική ανάπτυξη του Παγκόσμιου Ιστού και η συνεχής διασπορά του σε διάφορους τομείς της καθημερινότητας, έχει τροφοδοτήσει την ανάπτυξη μίας νέας γενιάς εφαρμογών, οι οποίες χαρακτηρίζονται πλέον από μεγάλο βαθμό πολυπλοκότητας. Η ανάπτυξη τέτοιων εφαρμογών είναι στην ουσία ένα υβρίδιο που συνδυάζει παραδοσιακά Πληροφοριακά Συστήματα με εφαρμογές Υπερμέσων (Hypermedia). Αυτός ο συνδυασμός θέτει νέες προκλήσεις στις υπάρχουσες προσεγγίσεις σχεδιασμού και παραγωγής λογισμικού. Στα πλαίσια της συγκεκριμένης διδακτορικής διατριβής, διερευνώνται θέματα βελτίωσης της απόδοσης εφαρμογών Παγκόσμιου Ιστού (ιδιαίτερα απαιτητικών σε δεδομένα - data intensive), σε ολόκληρο τον κύκλο ζωής τους. Βασικός στόχος είναι η βελτίωση της απόδοσης εφαρμογών, σε πρώτο επίπεδο στα πλαίσια του σχεδιασμού, ανάπτυξης και συντήρησης τους και σε δεύτερο επίπεδο στα πλαίσια της διάθεσής τους προς τον τελικό χρήστη. Στο πρώτο κεφάλαιο της διδακτορικής διατριβής παρουσιάζεται η τρέχουσα κατάσταση σε σχέση με τις μεθοδολογίες σχεδιασμού και ανάπτυξης εφαρμογών Παγκόσμιου Ιστού που έχουν προταθεί από την ερευνητική κοινότητα μέχρι σήμερα. Γίνεται μία προσπάθεια να αναγνωριστούν και να χαρακτηριστούν οι διάφορες κατηγορίες λύσεων και παρουσιάζεται μία πρώτου επιπέδου αξιολόγηση σε σχέση με την επάρκεια που παρουσιάζουν στις απαιτήσεις της διαδικασίας ανάπτυξης εφαρμογών Παγκόσμιου Ιστού. Επιπλέον, επισημαίνονται διάφορα ανοιχτά προβλήματα και αναλύονται οι πιθανές μελλοντικές τάσεις. Ακόμη, αναλύεται σε μεγαλύτερο βάθος η μεθοδολογία και η αντίστοιχη γλώσσα μοντελοποίησης εφαρμογών Παγκόσμιου Ιστού WebML, καθώς αποτελεί τη βάση (γλώσσα επίδειξης) πάνω στην οποία θα στηριχτεί η παρουσίαση των τεχνικών και μεθόδων που προτείνονται στα επόμενα δύο κεφάλαια της διδακτορικής διατριβής. Στη συνέχεια, συζητούνται θέματα σε σχέση με τη μεθοδολογική προσέγγιση που χρησιμοποιήθηκε για το σχεδιασμό συγκεκριμένων παραδειγμάτων πραγματικών εφαρμογών και αναλύονται τα πλεονεκτήματα και τα αντίστοιχα μειονεκτήματα που παρουσιάστηκαν. Το δεύτερο κεφάλαιο επικεντρώνεται σε θέματα αξιολόγησης και αναδιάταξης του εννοιολογικού σχήματος-μοντέλου εφαρμογών Παγκόσμιου Ιστού. Εισάγεται η έννοια των Κλώνων Μοντέλου (Model Clones), ως μικρότερα μοντέλα υπερκειμένου που επαναλαμβάνονται σε ένα ευρύτερο μοντέλο εφαρμογής και η έννοια των Οσμών Μοντέλου (Model Smells), ως ενδείξεις ύπαρξης κλώνων. Παρουσιάζεται μία μέθοδος ανίχνευσης πιθανών προβλημάτων αποδοτικότητας, συνέπειας, ευχρηστίας και ποιότητας στο επίπεδο του σχήματος υπερκειμένου της εφαρμογής μέσω της εξόρυξης κλώνων μοντέλου. Έτσι μπορεί να επιτευχθεί ο αποδοτικός επανασχεδιασμός και η βελτίωση της συνολικής ποιότητάς της, σε επίπεδο διαχείρισης δεδομένων, διάταξης του υπερκειμένου και παρουσίασης του περιεχομένου. Επιπλέον, παρέχονται μετρικές αξιολόγησης, οι οποίες δίνουν τη δυνατότητα ποσοτικοποίησης της "ακατάλληλης" επαναχρη-σιμοποίησης των κλώνων και προτείνονται κανόνες αναδιάταξης του μοντέλου της εφαρμογής. Τέλος, αναλύονται θέματα αυτοματοποίησης της διαδικασίας αναδιάταξης του μοντέλου της εφαρμογής με βάση τους κλώνους μοντέλου που έχουν ανιχνευθεί. Οι τεχνικές που παρουσιάζονται μπορούν να εφαρμοστούν κατά τη διάρκεια σχεδιασμού της εφαρμογής, καθώς και κατά τη διάρκεια συντήρησης και επανασχεδιασμού της. Βασικός στόχος είναι να υποστηριχτεί η ανάγκη να προσεγγιστούν όλες οι πτυχές αποδοτικού και ποιοτικού σχεδιασμού από την αρχή του κύκλου ανάπτυξης εφαρμογών Παγκόσμιου Ιστού. Στο τρίτο κεφάλαιο μελετάται το πρόβλημα εντοπισμού αποδοτικών σχεδιαστικών λύσεων και σχεδιαστικών προτύπων μέσα στο εννοιολογικό σχήμα-μοντέλο μίας ή περισσότερων εφαρμογών Παγκόσμιου Ιστού. Τα σχεδιαστικά πρότυπα παράγονται από πεπειραμένους σχεδιαστές λογισμικού, οι οποίοι εμπειρικά μελετούν μια σειρά από επιτυχημένες εφαρμογές και στη συνέχεια ορίζουν ένα ή περισσότερα από αυτά. Επιπλέον, το μεγαλύτερο ποσοστό σχεδιαστικών προτύπων μέχρι σήμερα, έχει προταθεί από ένα πολύ μικρό αριθμό σχεδιαστών. Με στόχο την αντιμετώπιση του παραπάνω προβλήματος, προτείνεται μία μέθοδος αυτόματης εξόρυξης αποτελεσματικών σχεδιαστικών λύσεων κατά τη διάρκεια σχεδίασης (ή συντήρησης και επανασχεδιασμού) μίας εφαρμογής, στο επίπεδο του μοντέλου της. Η συγκεκριμένη μεθοδολογική προσέγγιση, στην περίπτωση που εφαρμοστεί σε εννοιολογικά σχήματα πολλών εφαρμογών μίας συγκεκριμένης κατηγορίας, μπορεί να οδηγήσει στον προσδιορισμό Πλαισίων Ανάπτυξης Εφαρμογών για τον αποδοτικό σχεδιασμό εφαρμογών της συγκεκριμένης αυτής κατηγορίας, ή ακόμα και στον αυτόματο εντοπισμό σχεδιαστικών προτύπων. Τέλος, παρουσιάζεται ο συνδυασμός της μεθόδου με υψηλότερου επιπέδου γλώσσες χειρισμού μοντέλου εφαρμογών, ώστε να επιτευχθεί η αυτοματοποίηση της εφαρμογής των αποδοτικών σχεδιαστικών λύσεων που ανακτήθηκαν με τη χρήση της, για τη δημιουργία ή επέκταση του εννοιολογικού σχήματος μίας εφαρμογής. Στο τελευταίο κεφάλαιο της διδακτορικής διατριβής γίνεται διερεύνηση του προβλήματος της συνεχώς αυξανόμενης κίνησης στον Παγκόσμιο Ιστό και της επίδρασης που έχει αυτό στην ποιότητα των εφαρμογών που βασίζονται στο συγκεκριμένο περιβάλλον. Σύμφωνα με πρόσφατες έρευνες, η κίνηση στον Παγκόσμιο Ιστό διπλασιάζεται κάθε χρόνο. Οι χρήστες απαιτούν όλο και μεγαλύτερο όγκο πληροφορίας από τους Ιστοχώρους του Παγκόσμιου Ιστού, ενώ παράλληλα θέλουν να ξοδέψουν όσο το δυνατόν μικρότερο χρόνο για την καταφόρτωση δεδομένων (downloading). Για το λόγο αυτό, όλο και περισσότερο εύρος ζώνης Διαδικτύου απαιτείται και οι παροχείς πρόσβασης στο Διαδίκτυο (ISPs) προσπαθούν να λύσουν το πρόβλημα κατασκευάζοντας δίκτυα υψηλών ταχυτήτων. Στο συγκεκριμένο κεφάλαιο παρουσιάζεται μία μέθοδος μείωσης του χρόνου καταφόρτωσης ιστοσελίδων με τη χρήση αλγορίθμων συμπίεσης δεδομένων. Επίσης, παρουσιάζεται μια περιπτωσιολογική μελέτη (case study) που υπολογίζει τη μείωση του χρόνου που απαιτείται για να καταφορτωθεί πλήρως μία ιστοσελίδα και να παραδοθεί στον τελικό χρήστη. Επιπλέον, αναλύεται ο τρόπος υπολογισμού του ποσοστού μείωσης του όγκου των μεταφερόμενων δεδομένων, των πόρων σε εύρος ζώνης και του χρόνου απόκρισης, όταν το χαρακτηριστικό συμπίεσης του πρωτοκόλλου HTTP/1.1 ενεργοποιηθεί.
Open Access
Τεχνικές ελέγχου ορθής λειτουργίας με έμφαση στη χαμηλή κατανάλωση ισχύος
(2007-06-25T06:14:02Z) Μπέλλος, Μάτσιεϊ; Νικολός, Δημήτριος; Παλιουράς, Βασίλειος; Αλεξίου, Γεώργιος; Τσιατούχας, Γεώργιος; Γκούτης, Κωνσταντίνος; Βέργος, Χαρίδημος; Καβουσιανός, Χρυσοβαλάντης; Νικολός, Δημήτριος; Bellos, Maciej
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Η διατριβή ασχολείται με το αντικείμενο του ελέγχου ορθής λειτουργίας κυκλωμάτων κατά τον οποίο λαμβάνεται υπόψη και η συμπεριφορά ως προς την κατανάλωση ισχύος. Οι τεχνικές που προτείνονται αφορούν α) τη συμπίεση ενός συνόλου δοκιμής σε περιβάλλον ενσωματωμένου ελέγχου με χρήση εξωτερικών ελεγκτών, β) την εμφώλευση διανυσμάτων δοκιμής σε περιβάλλον ενσωματωμένου ελέγχου και γ) τη μείωση της κατανάλωση ισχύς και ενέργειας σε περιβάλλον εξωτερικού ελέγχου. Η συμπίεση των δεδομένων βασίζεται στην παρατήρηση ότι ένα διάνυσμα δοκιμής μπορεί να παραχθεί από το προηγούμενό του με την αντικατάσταση κάποιων τμημάτων του. Μεγαλύτερη συμπίεση επιτυγχάνεται όταν γίνει αναδιαταξή διανυσμάτων και αναδιάταξη των φλιπ-φλοπ της αλυσίδας ανίχνευσης. Αν η αναδιάταξη των φλιπ-φλοπ γίνει με βάση τη συχνότητα αλλαγών κατάστασης γειτονικών φλιπ-φλοπ τότε επιτυγχάνεται και μείωση της κατανάλωσης ισχύος. Όσον αφορά τις τεχνικές ενσωματωμένου αυτοελέγχου, μελετήθηκε το πρόβλημα της εμφώλευσης διανυσμάτων δοκιμής. Προτάθηκαν αποδοτικά κυκλώματα παραγωγής διανυσμάτων δοκιμής βασισμένα σε ολισθητές γραμμικής ανάδρασης και δέντρα πυλών XOR και σε ολισθητές συνδυασμένους με δέντρα πυλών OR. Όταν τα κυκλώματα υπό έλεγχο είναι κανονικής μορφής όπως είναι οι αθροιστές του αριθμητικού συστήματος υπολοίπων, προτείνονται κυκλώματα που εκμεταλεύονται την κανονική μορφή του συνόλου δοκιμής. Τέλος, σε περιβάλλον εξωτερικού ελέγχου, προτείνονται μέθοδοι αναδιάταξης διανυσμάτων δοκιμής με επανάληψη διανυσμάτων που μειώνουν την κατανάλωση. Οι μέθοδοι αυτές βασίζονται στην επιλογή των κατάλληλων ελάχιστων γεννητικών δέντρων και στη μετατροπή των κατάλληλων επαναλαμβανόμενων διανυσμάτων επιτυγχάνοντας σημαντική μείωση στην κατανάλωση ενέργειας, στη μέση και στη μέγιστη κατανάλωση ισχύος.
Open Access
Θεωρία και εφαρμογές κρυπτογραφικών συστημάτων δημόσιου κλειδιού βασισμένων σε ελλειπτικές καμπύλες
(2007-06-25T06:14:30Z) Κωνσταντίνου, Ελισάβετ; Ζαρολιάγκης, Χρήστος; Γαλλόπουλος, Ευστράτιος; Σταματίου, Ιωάννης; Βραχάτης, Μιχαήλ; Σπυράκης, Παύλος; Γκρίτζαλης, Στέφανος; Κακλαμάνης, Χρήστος; Ζαρολιάγκης, Χρήστος; Konstantinou, Elisavet
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Τα κρυπτογραφικά συστήματα που βασίζονται στις ελλειπτικές καμπύλες, αποτελούν ένα πολύ σημαντικό κομμάτι της κρυπτογραφίας δημόσιου κλειδιού και τα τελευταία χρόνια όλο και περισσότεροι επιστήμονες ασχολούνται με τη μελέτη τους. Το πλεονέκτημα των συστημάτων αυτών σε σχέση με τα συμβατικά κρυπτογραφικά συστήματα (π.χ. RSA) είναι ότι χρησιμοποιούν μικρότερες παραμέτρους και κλειδιά, προσφέροντας τα ίδια επίπεδα ασφάλειας. Για το λόγο αυτό, τα κρυπτογραφικά συστήματα ελλειπτικών καμπυλών προτιμούνται σε συσκευές περιορισμένων πόρων, όπως οι έξυπνες κάρτες (smart cards) και τα κινητά τηλέφωνα. Ένα από τα πιο θεμελιώδη προβλήματα στα κρυπτογραφικά συστήματα ελλειπτικών καμπυλών, είναι η γένεση ελλειπτικών καμπυλών, κατάλληλων να προσφέρουν την ασφάλεια που απαιτείται από τις κρυπτογραφικές εφαρμογές. Η πιο αποδοτική μέθοδος γένεσης ελλειπτικών καμπυλών, ορισμένων πάνω σε πρώτα, πεπερασμένα σώματα, είναι η μέθοδος του Μιγαδικού Πολλαπλασιασμού ή εν συντομία η μέθοδος CM. Η μέθοδος αυτή απαιτεί την εύρεση των ριζών ορισμένων πολυωνύμων, που ονομάζονται πολυώνυμα κλάσεως. Τα πολυώνυμα που χρησιμοποιούνται συνήθως είναι τα πολυώνυμα Hilbert και τα πολυώνυμα Weber. Τα πρώτα μπορούν να χρησιμοποιηθούν άμεσα στη μέθοδο CM, αλλά η κατασκευή τους είναι πολύ χρονοβόρα. Από την άλλη, τα πολυώνυμα Weber κατασκευάζονται πολύ πιο αποδοτικά αλλά δεν μπορούν να χρησιμοποιηθούν άμεσα στη μέθοδο CM. Για να γίνει αυτό, πρέπει οι ρίζες τους να μετασχηματιστούν στις ρίζες των αντίστοιχων πολυωνύμων Hilbert. Η παρούσα διδακτορική διατριβή στοχεύει σε τρεις κύριες κατευθύνσεις. Η πρώτη αφορά στη βελτίωση της απόδοσης της στη μεθόδου CM και στην εισαγωγή σε αυτή των πολυωνύμων Weber. Η δεύτερη, στην κατασκευή ελλειπτικών καμπυλών πρώτης τάξης. Η χρήση αυτών των ελλειπτικών καμπυλών εγγυάται τη σθεναρότητα των συστημάτων που τις χρησιμοποιούν απέναντι σε όλες τις πιθανές επιθέσεις. Η τρίτη αφορά στη δημιουργία μιας βιβλιοθήκης λογισμικού που να μπορεί να χρησιμοποιηθεί σε περιβάλλοντα περιορισμένων πόρων και η οποία να περιλαμβάνει όλους τους αλγορίθμους και τα πρωτόκολλα που απαιτούνται για την κατασκευή ενός ολοκληρωμένου κρυπτογραφικού συστήματος ελλειπτικών καμπυλών. Η πρώτη συνεισφορά της παρούσας διδακτορικής διατριβής αφορά σε μια νέα παραλλαγή της μεθόδου CM, η οποία βασίζεται στα πολυώνυμα Weber. Παρουσιάζεται το σύνολο των μετασχηματισμών των ριζών τους στις ρίζες των αντίστοιχων πολυωνύμων Hilbert και δίνεται ένα θεωρητικό άνω φράγμα για την ακρίβεια που απαιτείται για την κατασκευή τους. Επιπλέον, παρουσιάζεται μια εκτενής πειραματική μελέτη, με την οποία συγκρίνεται η χρήση των πολυωνύμων Hilbert με αυτή των πολυωνύμων Weber στη μέθοδο CM, καταδεικνύοντας τα πλεονεκτήματα των τελευταίων. Πειραματικά αποτελέσματα επίσης, αποδεικνύουν ότι το άνω φράγμα της ακρίβειας κατασκευής των πολυωνύμων Weber που παρουσιάστηκε στη διδακτορική διατριβή, είναι πολύ κοντά στην πραγματική ακρίβεια που απαιτείται για την κατασκευή τους. Η δεύτερη συνεισφορά αφορά στην κατασκευή ελλειπτικών καμπυλών πρώτης τάξης. Στην περίπτωση αυτή, αποδεικνύεται ότι τα πολυώνυμα Weber έχουν τρεις φορές μεγαλύτερο βαθμό από τον βαθμό των αντίστοιχων πολυωνύμων Hilbert, και μάλιστα τα συγκεκριμένα πολυώνυμα δεν έχουν ρίζες στα πρώτα πεπερασμένα σώματα (F_p), αλλά σε μια επέκτασή τους (F_{p^3}). Επιπλέον, παρουσιάζονται οι μετασχηματισμοί των ριζών των πολυωνύμων Weber (που ανήκουν τώρα στο F_{p^3}) στις ρίζες των αντίστοιχων πολυωνύμων Hilbert (που ανήκουν στο F_p). Ορίζονται επίσης κάποια νέα πολυώνυμα κλάσεως και μέσω μιας εκτενούς πειραματικής μελέτης συγκρίνεται η χρήση τους στη μέθοδο CM με αυτή των πολυωνύμων Weber, αποδεικνύοντας ότι ανάλογα με τις απαιτήσεις κάθε συστήματος, πρέπει να επιλέγεται διαφορετική κλάση πολυωνύμων. Επιπλέον, αναλύεται η αποδοτικότητα ενός σημαντικού βήματος της μεθόδου χρησιμοποιώντας τέσσερις διαφορετικούς αλγορίθμους και αποδεικνύεται ότι ο αλγόριθμος που προτείνεται στη διδακτορική διατριβή είναι ο δεύτερος καλύτερος ως προς τον χρόνο, αλλά έχει λιγότερες απαιτήσεις χώρου από τον γρηγορότερο. Τέλος, όσον αφορά στον τρίτο στόχο που τέθηκε στα πλαίσια της διδακτορικής διατριβής, παρουσιάζεται η υλοποίηση μιας βιβλιοθήκης λογισμικού που μπορεί να χρησιμοποιηθεί για την ανάπτυξη κρυπτογραφικών συστημάτων ελλειπτικών καμπυλών σε περιβάλλοντα περιορισμένων πόρων. Η βιβλιοθήκη είναι οργανωμένη σε διάφορα, καθαρά διαχωρίσιμα μεταξύ τους τμήματα, έτσι ώστε να μπορεί έυκολα να τροποποιηθεί ανάλογα με τις ανάγκες και τις απαιτήσεις κάθε χρήστη.
Open Access
Τεχνικές και συστήματα διαχείρισης γνώσης στο διαδίκτυο
(2007-06-25T06:15:07Z) Μαρκέλλου, Πηνελόπη; Τσακαλίδης, Αθανάσιος; Παυλίδης, Γεώργιος; Γαροφαλάκης, Ιωάννης; Χατζηλυγερούδης, Ιωάννης; Λυκοθανάσης, Σπυρίδων; Νικολετσέας, Σωτήριος; Μακρής, Χρήστος; Τσακαλίδης, Αθανάσιος; Markellou, Pinelopi
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Ο Παγκόσμιος Ιστός Πληροφοριών (Web) χαρακτηρίζεται σαν ένα περιβάλλον αχανές, ετερογενές, κατανεμημένο και πολύπλοκο με αποτέλεσμα να είναι δύσκολος ο αποδοτικός χειρισμός των δεδομένων των e-εφαρμογών με βάση παραδοσιακές μεθόδους και τεχνικές. Αυτό με τη σειρά του οδηγεί στην απαίτηση για σχεδιασμό, ανάπτυξη και υιοθέτηση «ευφυών» εργαλείων που θα επιλέξουν και θα εμφανίσουν στο χρήστη την κατάλληλη πληροφορία, στον κατάλληλο χρόνο και με την κατάλληλη μορφή. Η παρούσα διδακτορική διατριβή ασχολείται με το πρόβλημα της εξόρυξης «κρυμμένης» γνώσης από συστήματα και εφαρμογές ηλεκτρονικής μάθησης (e-learning), ηλεκτρονικού εμπορίου (e-commerce) και επιχειρηματικής ευφυΐας (business intelligence) με κύριο στόχο τη βελτίωση της ποιότητας και της απόδοσης των παρεχόμενων υπηρεσιών προς τους τελικούς χρήστες. Συγκεκριμένα, τα ερευνητικά αποτελέσματα επικεντρώνονται στα ακόλουθα: α) Μεθοδολογίες, τεχνικές και προτεινόμενοι αλγόριθμοι εξόρυξης «κρυμμένης» γνώσης από e-εφαρμογές λαμβάνοντας υπόψη τη σημασιολογία των δεδομένων, β) Παραγωγή εξατομικευμένων εκπαιδευτικών εμπειριών, γ) Παραγωγή αποδοτικών συστάσεων για την αγορά online προϊόντων, δ) Παραγωγή επιστημονικών και τεχνολογικών δεικτών από διπλώματα ευρεσιτεχνίας για την ανάδειξη του επιπέδου καινοτόμου δραστηριότητας μιας αγοράς, ε) Προτάσεις για μελλοντικές ερευνητικές κατευθύνσεις που επεκτείνουν τις τεχνικές εξόρυξης γνώσης σε πιο σύνθετους τύπους εφαρμογών και αναδεικνύουν νέες ερευνητικές ευκαιρίες. Στο πρώτο κεφάλαιο παρουσιάζεται μια προσέγγιση για την υποστήριξη εξατομικευμένου e-learning όπου η δομή και η σχέση των δεδομένων και των πληροφοριών παίζουν ουσιαστικό ρόλο. Ο προτεινόμενος αλγόριθμος βασίζεται σε μια οντολογία (ontology) η οποία βοηθά στη δόμηση και στη διαχείριση του περιεχομένου που σχετίζεται με μια δεδομένη σειρά μαθημάτων, ένα μάθημα ή ένα θεματικό. Η διαδικασία χωρίζεται σε δύο στάδια: στις offline ενέργειες προετοιμασίας των δεδομένων, δημιουργίας της οντολογίας και εξόρυξης από δεδομένα χρήσης (usage mining) και στην online παροχή της εξατομίκευσης. Το σύστημα βρίσκει σε πρώτη φάση ένα αρχικό σύνολο συστάσεων βασισμένο στην οντολογία του πεδίου και στη συνέχεια χρησιμοποιεί τα frequent itemsets (συχνά εμφανιζόμενα σύνολα στοιχείων) για να το εμπλουτίσει, λαμβάνοντας υπόψη την πλοήγηση άλλων παρόμοιων χρηστών (similar users). Με τον τρόπο αυτό, μειώνουμε το χρόνο που απαιτείται για την ανάλυση όλων των frequent itemsets και των κανόνων συσχέτισης. Εστιάζουμε μόνο σε εκείνα τα σύνολα που προέρχονται από το συνδυασμό της ενεργούς συνόδου (current session) του χρήστη και των συστάσεων της οντολογίας. Επιπλέον, αυτή η προσέγγιση ανακουφίζει και το πρόβλημα των μεγάλων χρόνων απόκρισης, το οποίο μπορεί στη συνέχεια να οδηγήσει στην εγκατάλειψη του e-learning συστήματος. Αν και η εξατομίκευση απαιτεί αρκετά βήματα επεξεργασίας και ανάλυσης, το εμπόδιο αυτό αποφεύγεται με την εκτέλεση σημαντικού μέρους της διαδικασίας offline. Στο δεύτερο κεφάλαιο μελετάται το πρόβλημα της παραγωγής προτάσεων σε μια εφαρμογή e-commerce. Τα συστήματα συστάσεων (recommendations systems ή RSs) αποτελούν ίσως την πιο δημοφιλή μορφή εξατομίκευσης και τείνουν να μετατραπούν στις μέρες μας σε σημαντικά επιχειρησιακά εργαλεία. Η προτεινόμενη υβριδική προσέγγιση στοχεύει στην παραγωγή αποτελεσματικών συστάσεων για τους πελάτες ενός online καταστήματος που νοικιάζει κινηματογραφικές ταινίες. Η γνώση για τους πελάτες και τα προϊόντα προκύπτει από δεδομένα χρήσης και τη δομή της οντολογίας σε συνδυασμό με τις εκτιμήσεις-βαθμολογίες των πελατών για τις ταινίες καθώς και την εφαρμογή τεχνικών ταιριάσματος «όμοιων» πελατών. Όταν ένα ή περισσότερα κριτήρια ταιριάσματος ικανοποιούνται, τότε άλλες ταινίες μπορούν να προσδιοριστούν σύμφωνα με το οντολογικό σχήμα που έχουν παρόμοια χαρακτηριστικά με αυτές που ο πελάτης έχει ήδη νοικιάσει. Στην περίπτωση ενός νέου πελάτη όπου το ιστορικό του είναι κενό, πληροφορίες από την αίτηση εγγραφής του αναλύονται ώστε να ταξινομηθεί σε μια συγκεκριμένη κλάση πελατών και να παραχθούν προτάσεις με βάση το οντολογικό σχήμα. Αυτή η ολοκλήρωση παρέχει πρόσθετη γνώση για τις προτιμήσεις των πελατών και επιτρέπει την παραγωγή επιτυχημένων συστάσεων. Ακόμη και στην περίπτωση του «cold-start problem» όπου δεν είναι διαθέσιμη αρχική πληροφορία για τη συμπεριφορά του πελάτη, η προσέγγιση μπορεί να προβεί σε σχετικές συστάσεις. Τέλος, στο τρίτο κεφάλαιο μελετάται το πρόβλημα της εξόρυξης γνώσης από καταχωρήσεις διπλωμάτων ευρεσιτεχνίας που καταδεικνύουν το επίπεδο της καινοτόμου δραστηριότητας μιας αγοράς. Η προτεινόμενη προσέγγιση αφορά στην εφαρμογή τεχνικών Text Mining σε διπλώματα ευρεσιτεχνίας που βρίσκονται καταχωρημένα σε βάσεις δεδομένων διαφόρων διεθνών οργανισμών διαχείρισής τους, με στόχο την παραγωγή επιστημονικών και τεχνολογικών δεικτών για την ανάδειξη του επιπέδου καινοτομίας μιας αγοράς και συνεπώς την επιχειρηματική ευφυΐα. Αρχικά τα δεδομένα καθαρίζονται προκειμένου να βελτιωθεί η ποιότητά τους πριν την επεξεργασία. Στη συνέχεια εφαρμόζονται δύο τύποι επεξεργασίας η απλή ανάλυση (simple analysis) και η στατιστική ανάλυση (statistical analysis). Στην πρώτη περίπτωση παράγονται γραφήματα που συσχετίζουν τις πληροφορίες π.χ. κύριοι τομείς ανάπτυξης σε μια χώρα. Στη δεύτερη περίπτωση αναλύονται γλωσσολογικά τα πεδία title και abstract των διπλωμάτων ευρεσιτεχνίας και ομαδοποιούνται τα λήμματα των λέξεων. Στη συνέχεια πάνω στα δεδομένα εφαρμόζονται τεχνικές correspondence και clustering analysis έτσι ώστε αυτά να ομαδοποιηθούν σύμφωνα με τις τεχνολογίες στις οποίες αναφέρονται. Τα clusters πλέον αυτά προβάλλονται όπως και στην απλή ανάλυση παρέχοντας στο χρήστη μια πιο λεπτομερή απεικόνιση της πληροφορίας των διπλωμάτων ευρεσιτεχνίας. Ο συνδυασμός των αναλύσεων που εφαρμόζονται με βάση την προτεινόμενη μεθοδολογία επιτρέπει την αποτύπωση των τεχνολογικών εξελίξεων και καινοτομιών. Οι δείκτες που παράγονται είναι πολύ σημαντικοί αφού μπορούν να ποσοτικοποιήσουν τις πληροφορίες που αφορούν σε συγκεκριμένες τεχνολογίες. Με αυτό τον τρόπο μπορούμε να παράγουμε δείκτες για τη δραστηριότητα συγκεκριμένων φορέων, εφευρετών, χωρών, κλπ. Τέλος, τεχνολογικοί δείκτες που υποδεικνύουν μελλοντικές ελπιδοφόρες τεχνολογίες καθώς και ποιοι φορείς θα είναι πρωτοπόροι σε αυτές μπορούν να εξαχθούν.
Open Access
Χωροχρονικές τεχνικές επεξεργασίας σήματος σε ασύρματα τηλεπικοινωνιακά δίκτυα
(2007-10-25T07:47:35Z) Κεκάτος, Βασίλειος; Μπερμπερίδης, Κωνσταντίνος; Μπερμπερίδης, Κωνσταντίνος; Βαρβαρίγος, Εμμανουήλ; Θεοδωρίδης, Σέργιος; Γαλλόπουλος, Ευστράτιος; Παλιουράς, Βασίλειος; Ψαράκης, Εμμανουήλ; Ροντογιάννης, Αθανάσιος; Kekatos, Vassilis
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Τα τελευταία χρόνια χαρακτηρίζονται από μια αλματώδη ανάπτυξη των προϊόντων και υπηρεσιών που βασίζονται στα δίκτυα ασύρματης επικοινωνίας, ενώ προκύπτουν σημαντικές ερευνητικές προκλήσεις. Τα συστήματα πολλαπλών κεραιών στον πομπό και στο δέκτη, γνωστά και ως συστήματα MIMO (multi-input multi-output), καθώς και η τεχνολογία πολλαπλής προσπέλασης με χρήση κωδικών (code division multiple access, CDMA) αποτελούν δύο από τα βασικά μέτωπα ανάπτυξης των ασύρματων τηλεπικοινωνιών. Στα πλαίσια της παρούσας διδακτορικής διατριβής, ασχοληθήκαμε με την ανάπτυξη και μελέτη αλγορίθμων επεξεργασίας σήματος για τα δύο παραπάνω συστήματα, όπως περιγράφεται αναλυτικά παρακάτω. Σχετικά με τα συστήματα MIMO, η πρωτοποριακή έρευνα που πραγματοποιήθηκε στα Bell Labs γύρω στα 1996, όπου αναπτύχθηκε η αρχιτεκτονική BLAST (Bell Labs Layered Space-Time), απέδειξε ότι η χρήση πολλαπλών κεραιών μπορεί να οδηγήσει σε σημαντική αύξηση της χωρητικότητας των ασύρματων συστημάτων. Προκειμένου να αξιοποιηθούν οι παραπάνω δυνατότητες, απαιτείται η σχεδίαση σύνθετων δεκτών MIMO. Προς αυτήν την κατεύθυνση, έχει προταθεί ένας μεγάλος αριθμός μεθόδων ισοστάθμισης του καναλιού. Ωστόσο, οι περισσότερες από αυτές υποθέτουν ότι το ασύρματο κανάλι είναι: 1) χρονικά σταθερό, 2) συχνοτικά επίπεδο (δεν εισάγει διασυμβολική παρεμβολή), και κυρίως 3) ότι είναι γνωστό στο δέκτη. Δεδομένου ότι σε ευρυζωνικά συστήματα μονής φέρουσας οι παραπάνω υποθέσεις είναι δύσκολο να ικανοποιηθούν, στραφήκαμε προς τις προσαρμοστικές μεθόδους ισοστάθμισης. Συγκεκριμένα, αναπτύξαμε τρεις βασικούς αλγορίθμους. Ο πρώτος αλγόριθμος αποτελεί έναν προσαρμοστικό ισοσταθμιστή ανάδρασης αποφάσεων (decision feedback equalizer, DFE) για συχνοτικά επίπεδα κανάλια ΜΙΜΟ. Ο προτεινόμενος MIMO DFE ακολουθεί την αρχιτεκτονική BLAST, και ανανεώνεται με βάση τον αλγόριθμο αναδρομικών ελαχίστων τετραγώνων (RLS) τετραγωνικής ρίζας. Ο ισοσταθμιστής μπορεί να παρακολουθήσει ένα χρονικά μεταβαλλόμενο κανάλι, και, από όσο γνωρίζουμε, έχει τη χαμηλότερη πολυπλοκότητα από όλους τους δέκτες BLAST που έχουν προταθεί έως σήμερα. Ο δεύτερος αλγόριθμος αποτελεί την επέκταση του προηγούμενου σε συχνοτικά επιλεκτικά κανάλια. Μέσω κατάλληλης μοντελοποίησης του προβλήματος ισοστάθμισης, οδηγηθήκαμε σε έναν αποδοτικό DFE για ευρυζωνικά κανάλια MIMO. Τότε, η διαδικασία της ισοστάθμισης εμφανίζει προβλήματα αριθμητικής ευστάθειας, που λόγω της υλοποίησης RLS τετραγωνικής ρίζας αντιμετωπίστηκαν επιτυχώς. Κινούμενοι προς την κατεύθυνση περαιτέρω μείωσης της πολυπλοκότητας, προτείναμε έναν προσαρμοστικό MIMO DFE που ανανεώνεται με βάση τον αλγόριθμο ελαχίστων μέσων τετραγώνων (LMS) υλοποιημένο εξ ολοκλήρου στο πεδίο της συχνότητας. Με χρήση του ταχύ μετασχηματισμού Fourier (FFT), μειώνεται η απαιτούμενη πολυπλοκότητα. Παράλληλα, η μετάβαση στο πεδίο των συχνοτήτων έχει ως αποτέλεσμα την προσεγγιστική διαγωνοποίηση του συστήματος, προσφέροντας ανεξάρτητη ανανέωση των φίλτρων ανά συχνοτική συνιστώσα και επιτάχυνση της σύγκλισης του αλγορίθμου. Ο προτεινόμενος ισοσταθμιστής πετυχαίνει μια καλή ανταλλαγή μεταξύ απόδοσης και πολυπλοκότητας. Παράλληλα με τα παραπάνω, ασχοληθήκαμε με την εκτίμηση του ασύρματου καναλιού σε ένα ασύγχρονο σύστημα CDMA. Το βασικό σενάριο είναι ότι ο σταθμός βάσης γνωρίζει ήδη τους ενεργούς χρήστες, και καλείται να εκτιμήσει τις παραμέτρους του καναλιού ανερχόμενης ζεύξης ενός νέου χρήστη που εισέρχεται στο σύστημα. Το πρόβλημα περιγράφεται από μια συνάρτηση ελαχίστων τετραγώνων, η οποία είναι γραμμική ως προς τα κέρδη του καναλιού, και μη γραμμική ως προς τις καθυστερήσεις του. Αποδείξαμε ότι το πρόβλημα έχει μια προσεγγιστικά διαχωρίσιμη μορφή, και προτείναμε μια επαναληπτική μέθοδο υπολογισμού των παραμέτρων. Ο προτεινόμενος αλγόριθμος δεν απαιτεί κάποια ειδική ακολουθία διάχυσης και λειτουργεί αποδοτικά ακόμη και για περιορισμένη ακολουθία εκπαίδευσης. Είναι εύρωστος στην παρεμβολή πολλαπλών χρηστών και περισσότερο ακριβής από μια υπάρχουσα μέθοδο εις βάρος μιας ασήμαντης αύξησης στην υπολογιστική πολυπλοκότητα.
Open Access
Αλγόριθμοι ελαχιστοποίησης κατανάλωσης ενέργειας σε ασύρματα δίκτυα
(2007-11-23T10:10:48Z) Κανελλόπουλος, Παναγιώτης; Κακλαμάνης, Χρήστος; Κακλαμάνης, Χρήστος; Κυρούσης, Ελευθέριος; Σπυράκης, Παύλος; Βαρβαρίγος, Εμμανουήλ; Κοσμαδάκης, Σταύρος; Νικολετσέας, Σωτήριος; Καραγιάννης, Ιωάννης; Kanellopoulos, Panagiotis
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Στην παρούσα διδακτορική διατριβή ασχολούμαστε με ζητήματα ελαχιστοποίησης της κατανάλωσης ενέργειας που ανακύπτουν σε ασύρματα δίκτυα. Εξετάζουμε τόσο την περίπτωση ασυρμάτων δικτύων τύπου ad hoc όσο και την περίπτωση όπου υπάρχει ένα σταθερό ενσύρματο δίκτυο το οποίο συνδέει τους σταθμούς εκπομπής, οι οποίοι χρησιμοποιούν ασύρματα μέσα προκειμένου να μεταδώσουν μηνύματα στους χρήστες. Στην πρώτη κατηγορία, μελετούμε τόσο περιπτώσεις όπου η συνάρτηση κόστους στις ακμές είναι συμμετρική, όσο και περιπτώσεις όπου δεν ισχύει αυτή η υπόθεση. Εξετάζουμε επιπλέον προβλήματα που προκύπτουν όταν θεωρούμε ότι οι σταθμοί βρίσκονται σε κάποιον Ευκλείδειο χώρο και η απόσταση εξαρτάται από την Ευκλείδεια απόσταση. Παρουσιάζουμε αποτελέσματα υπολογιστικής δυσκολίας για την εύρεση τόσο της βέλτιστης λύσης όσο και μιας καλής προσεγγιστικής λύσης. Από την άλλη πλευρά, αποδεικνύουμε άνω φράγματα στον λόγο προσέγγισης διάφορων πολυωνυμικών αλγορίθμων. Στην περίπτωση που θεωρούμε πως οι σταθμοί μετάδοσης είναι συνδεδεμένοι με ένα ενσύρματο δίκτυο, έχουμε το πρόβλημα της συσταδοποίησης. Παρουσιάζουμε έναν βέλτιστο πολυωνυμικό αλγόριθμο για την περίπτωση όπου τα σημεία είναι συνευθειακά, ενώ αποδεικνύουμε αποτελέσματα υπολογιστικής δυσκολίας για την περίπτωση των δύο ή περισσοτέρων διαστάσεων. Τέλος, παρουσιάζουμε έναν προσεγγιστικό αλγόριθμο του οποίου ο λόγος προσέγγισης μπορεί να πλησιάσει αυθαίρετα κόντα το 1, με άλλα λόγια παρουσιάζουμε ένα προσεγγιστικό σχήμα πολυωνυμικού χρόνου.
Open Access
Δενδρικές δομές διαχείρισης πληροφορίας και βιομηχανικές εφαρμογές
(2008-02-06T07:24:43Z) Σοφοτάσιος, Δημήτριος; Τσακαλίδης, Αθανάσιος; Τσακαλίδης, Αθανάσιος; Σπυράκης, Παύλος; Γαροφαλάκης, Ιωάννης; Παυλίδης, Γεώργιος; Χατζηλυγερούδης, Ιωάννης; Μακρής, Χρήστος; Σταματίου, Ιωάννης; Sofotassios, Dimitrios
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
H διατριβή διερευνά προβλήματα αποδοτικής οργάνωσης χωροταξικών δεδομένων, προτείνει συγκεκριμένες δενδρικές δομές για τη διαχείρισή τους και, τέλος, δίνει παραδείγματα χρήσης τους σε ειδικές περιοχές εφαρμογών. Το πρώτο κεφάλαιο ασχολείται με το γεωμετρικό πρόβλημα της εύρεσης των ισo-προσανατολισμένων ορθογωνίων που περικλείουν ένα query αντικείμενο που μπορεί να είναι ένα ισο-προσανατολισμένο ορθογώνιο είτε σημείο ή κάθετο / οριζόντιο ευθύγραμμο τμήμα. Για την επίλυσή του προτείνεται μια πολυεπίπεδη δενδρική δομή που βελτιώνει τις πολυπλοκότητες των προηγούμενων καλύτερων λύσεων. Το δεύτερο κεφάλαιο εξετάζει το πρόβλημα της ανάκτησης σημείων σε πολύγωνα. H προτεινόμενη γεωμετρική δομή είναι επίσης πολυεπίπεδη και αποδοτική όταν το query πολύγωνο έχει συγκεκριμένες ιδιότητες. Το τρίτο κεφάλαιο ασχολείται με την εφαρμογή δενδρικών δομών σε δύο βιομηχανικά προβλήματα. Το πρώτο αφορά στη μείωση της πολυπλοκότητας ανίχνευσης συγκρούσεων κατά την κίνηση ενός ρομποτικού βραχίονα σε μια επίπεδη σκηνή με εμπόδια. Ο αλγόριθμος επίλυσης κάνει χρήση μιας ουράς προτεραιότητας και μιας UNION-FIND δομής ενώ αξιοποιεί γνωστές δομές και αλγόριθμους της Υπολογιστικής Γεωμετρίας όπως υπολογισμός κυρτών καλυμμάτων, έλεγχος polygon inclusion, κλπ. Το δεύτερο πρόβλημα ασχολείται με το σχεδιασμό απαιτήσεων υλικών (MRP) σε ένα βιομηχανικό σύστημα παραγωγής. Για το σκοπό αυτό αναπτύχθηκε ένας MRP επεξεργαστής που χρησιμοποιεί διασυνδεμένες λίστες και εκτελείται στην κύρια μνήμη για να είναι αποδοτικός. Το τελευταίο κεφάλαιο εξετάζει το πρόβλημα του ελέγχου της παραγωγής και συγκεκριμένα της δρομολόγησης εργασιών. Στο πλαίσιο αυτό σχεδιάστηκε και υλοποιήθηκε ένα ευφυές σύστημα δρομολόγησης σε περιβάλλον ροής που συνδυάζει γνωσιακή τεχνολογία και προσομοίωση με on-line έλεγχο προκειμένου να υποστηρίξει το διευθυντή παραγωγής στη λήψη αποφάσεων.
Open Access
Σχεδιασμός αλγορίθμων και υλοποίηση εφαρμογών για νέες υπηρεσίες
(2008-02-12T07:47:03Z) Καπούλας, Ευάγγελος; Σπυράκης, Παύλος; Σπυράκης, Παύλος; Κυρούσης, Λευτέρης; Τσακαλίδης, Αθανάσιος; Κακλαμάνης, Χρήστος; Μπούρας, Χρήστος; Γαραφαλάκης, Γιάννης; Λυκοθανάσης, Σπύρος; Kapoulas, Vaggelis
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Στη διατριβή εξετάζουμε προβλήματα που σχετίζονται με τη μετάδοση δεδομένων με υψηλές απαιτήσεις σε εύρος ζώνης και προτείνουμε λύσεις, αλγόριθμους, τεχνικές βελτίωσης της απόδοσης, και εφαρμογές που τις υλοποιούν. Για την περίπτωση του προβλήματος της μετάδοσης βίντεο κατ' απαίτηση (Video on Demand - VoD), εξετάζουμε το πρόβλημα της αποδοχής ή της απόρριψης αιτήσεων για μετάδοση ταινιών χωρίς να υπάρχει γνώση των μελλοντικών αιτήσεων. Παρουσιάζουμε έναν, άμεσης απόκρισης (online), πιθανοτικό αλγόριθμο χρονοπρογραμματισμού ταινιών που εκμεταλλεύεται την γνώση για την κατανομή των προτιμήσεων των αιτήσεων για ταινίες, και αποδεικνύουμε πως έχει ανταγωνιστικό λόγο (competitive ratio) που φράσσεται άνω από σταθερά. Επίσης, δείχνουμε πως η μέθοδος μας μπορεί να επεκταθεί σε ένα προσαρμοζόμενο αλγόριθμο που δεν γνωρίζει την κατανομή των προτιμήσεων. Επίσης, προτείνουμε έναν τρόπο να εφαρμόσουμε μια υπηρεσία βίντεο κατ' απαίτηση για ένα, βασισμένο στο πρωτόκολλο IP, δίκτυο, με περιορισμένο εύρος ζώνης. Στη συνέχεια, εξετάζουμε ένα σχήμα ελέγχου και διαχείρισης του εύρους ζώνης και παρουσιάζουμε ορισμένες μεθόδους προκειμένου να αυξήσουμε την αποδοτικότητα του συστήματος και την εκμετάλλευση του διαθέσιμου εύρους ζώνης (bandwidth). Εξετάζουμε διάφορες τεχνικές και παρουσιάζουμε πειραματικά αποτελέσματα για την βελτίωση της απόδοσης. Επίσης, σχεδιάζουμε και υλοποιούμε μια υπηρεσία διαχείρισης εύρους ζώνης (Managed Bandwidth Service -- MBS). Τέλος παρουσιάζουμε μια ενοποιημένη προσέγγιση για την μετάδοση υπερμεσικών/πολυμεσικών αντικειμένων, τα οποία παρουσιάζονται με βάση προκαθορισμένα σενάρια παρουσίασης (με χωροχρονικές αλληλοεξαρτήσεις μεταξύ των διάφορων μέσων). Τα υπερμεσικά αντικείμενα δομούνται σύμφωνα με μία γλώσσα σηματοδότησης, μέσω της οποίας διατηρούνται πληροφορίες για τις χωρικές και χρονικές συσχετίσεις. Επίσης, υλοποιούμε ένα τέτοιο σύστημα μετάδοσης, που εφαρμόζουμε για εκπαίδευση από απόσταση.
Open Access
Αυτοματοποιημένη διαχείριση υπηρεσιών quality of service
(2008-03-27T12:01:43Z) Πρίμπας, Δημήτριος; Μπούρας, Χρήστος; Μπούρας, Χρήστος; Αλεξίου, Γεώργιος; Βαρβαρίγος, Εμμανουήλ; Βλάχος, Κυριάκος; Γαροφαλάκης, Ιωάννης; Λυκοθανάσης, Σπυρίδων; Χριστοδουλάκης, Δημήτριος; Primpas, Dimitrios
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Η συνεχής εξέλιξη των δικτύων που βασίζονται στο ΙΡ πρωτόκολλο και η ευρύτατη διάδοση και χρήση τους τα τελευταία χρόνια σε ολόκληρο τον κόσμο καθοδηγεί την ανάγκη για την ανάπτυξη νέων τεχνολογιών και την αναβάθμιση των υπαρχόντων, προκειμένου να καλυφθούν οι συνεχώς μεταβαλλόμενες τάσεις και ανάγκες. Δύο από τις βασικότερες εξελίξεις που σχετίζονται με το επίπεδο του ΙΡ πρωτοκόλλου είναι η δυνατότητα για την παροχή εγγυήσεων ποιότητας (Quality of Service) σε τμήμα της συνολικής κίνησης που διακινείται μέσα από τα ΙΡ δίκτυα, καθώς και η ανάγκη αναβάθμισης του IPv4 πρωτοκόλλου προκειμένου (κυρίως) να εξαλειφθεί το πρόβλημα της φειδωλής διάθεσης μοναδικών και οικουμενικά δρομολογήσιμων διευθύνσεων, καθώς και να βελτιωθούν άλλες δευτερεύουσες ατέλειες του IPv4. Κεντρικό αντικείμενο αυτής της Διδακτορικής Διατριβής αποτελεί η μελέτη των τεχνολογιών για παροχή Quality of Service καθώς και η ανάπτυξη μηχανισμών και αλγορίθμων για την αποδοτική διαχείριση των πόρων, τον όσο το δυνατόν δίκαιο καταμερισμό της ποιότητας υπηρεσίας, καθώς και τη δυνατότητα συνεργασίας και διαλειτουργικότητας μεταξύ διαφορετικών αυτόνομων δικτυακών τμημάτων με αυτοματοποιημένο τρόπο (χωρίς δηλαδή να χρειάζεται η παρέμβαση ενός ανθρώπου διαχειριστή στις περισσότερες περιπτώσεις). Για το σκοπό αυτό έχουν προταθεί διάφορες προσεγγίσεις, οι οποίες μελετώνται στην εργασία αυτή, ενώ προτείνονται αλγόριθμοι και μηχανισμοί για τη βελτίωση της λειτουργίας και της απόδοσής τους. Επίσης, από το RFC 2638 της IETF έχει οριστεί η μονάδα του Bandwidth Broker που διαχειρίζεται συνολικά υπηρεσίες QoS σε ένα domain. Οι Bandwidth Brokers χρειάζεται να εγκαθιδρύσουν σχέσεις περιορισμένης εμπιστοσύνης με τις αντίστοιχες μονάδες στα γειτονικά domains, αντίθετα με άλλες αρχιτεκτονικές που απαιτούν τον καθορισμό των χαρακτηριστικών μιας ροής στους δρομολογητές κατά μήκος του από άκρο σε άκρο μονοπατιού. Επομένως η αρχιτεκτονική του Bandwidth Broker δίνει τη δυνατότητα να κρατηθεί η πληροφορία στο επίπεδο του διαχειριστικού domain, αντί να πρέπει να κρατηθεί σε κάθε δρομολογητή, και η DiffServ αρχιτεκτονική δίνει τη δυνατότητα να περιοριστεί η πληροφορία αυτή μόνο για τους ακραίους δρομολογητές κάθε domain. Στα πλαίσια της διδακτορικής αυτής διατριβής μελετήθηκε η αρχιτεκτονική DiffServ σε επίπεδο μηχανισμών χρησιμοποιώντας εργαλεία εξομοίωσης (NS-2 simulator) καθώς και πραγματικό δίκτυο ευρείας κλίμακας. Το IPv4 πρωτόκολλο έχει τη δυνατότητα υλοποίησης μηχανισμών QoS στο επίπεδο δικτύου με τη χρήση του πεδίου TOS (Type Of Service). Το IPv6 επεκτείνει και βελτιώνει την ιδέα αυτή, παρέχοντας δύο νέα πεδία στην στάνταρ επικεφαλίδα, τα Traffic Class και Flow Label, τα οποία μπορούν να χρησιμοποιηθούν προς αυτήν την κατεύθυνση. Το αποτέλεσμα ήταν ο σχεδιασμός μιας ομάδας υπηρεσιών QoS (απόλυτης προτεραιότητας σε IP κίνηση, εγγυημένου εύρους ζώνης για L2 συνδέσεις μέσω ιδεατών δικτύων καθώς και κίνησης χαμηλής προτεραιότητας). Ο σχεδιασμός αυτός ολοκληρώθηκε με την υλοποίηση μιας πλήρους εφαρμογής bandwidth broker (κεντρικοποιημένη αρχιτεκτονική) που εκτελεί τις ακόλουθες εργασίες: μοντελοποίηση δικτύου, εφαρμογή του μοντέλου διαστασιολόγησης στην τρέχουσα κατάσταση, αποδοχή κλήσης QoS αιτημάτων, παραγωγή παραμέτρων ρύθμισης για τις δικτυακές συσκευές, παρακολούθηση λειτουργίας QoS στο δίκτυο, επικοινωνία με αντίστοιχους bandwidth brokers σε γειτονικά domains και πλήρη διαχείριση των αιτημάτων QoS. Επιπλέον, δεδομένου ότι οι ανάγκες των εφαρμογών για QoS αυξάνονται, πρέπει να δίνεται μεγαλύτερη ευελιξία μια QoS σηματοδοσία. Για το λόγο αυτό μελετήθηκε και υλοποιήθηκε μια εφαρμογή αυτόματης σηματοδοσίας χρησιμοποιώντας το ευρέως γνωστό πρωτόκολλο δρομολόγησης BGP. Το αποτέλεσμα είναι να επιτυγχάνεται δυναμική σηματοδοσία για QoS σε ένα δίκτυο μέσω μιας διεπαφής που βασίζεται σε Web service ή σε μια Βάση Δεδομένων. Το σύνολο της εργασίας αυτής δοκιμάστηκε και εφαρμόστηκε στο Εθνικό Δίκτυο Έρευνας & Τεχνολογίας και είναι διαθέσιμο σε αντίστοιχα ερευνητικά εθνικά δίκτυα. Επιπλέον, μια σημαντική παράμετρος της υποστήριξης QoS μηχανισμών από άκρο σε άκρο είναι η συνεργασία μεταξύ διαφορετικών αυτόνομων τμημάτων (domains) που απαιτείται προκειμένου η κίνηση να υφίσταται προνομιακή μεταχείριση καθ’ όλη τη διαδρομή της και να της παρέχονται οι αναγκαίες εγγυήσεις ποιότητας. Η διαπραγμάτευση της συνεργασίας αυτής είναι σαφές ότι πρέπει να είναι όσο το δυνατόν αυτοματοποιημένη για να μπορούν τέτοιου είδους υπηρεσίες να γνωρίσουν ευρύτερη διάδοση. Ο υλοποιημένος bandwidth broker επεκτάθηκε ώστε μέσω Web service διεπαφών να «συνομιλεί» με αντίστοιχους άλλων domains. Παράλληλα, στα πλαίσια της εργασίας αυτής ασχοληθήκαμε επίσης με κατανεμημένες αρχιτεκτονικές bandwidth broker όπου έγιναν υλοποιήσεις σε επίπεδο εξομοίωσης. Αρχικά υλοποιήθηκαν ή επεκτάθηκαν οι υλοποιήσεις των μηχανισμών QoS στον εξομοιωτή και δημιουργήθηκε και δοκιμάστηκαν QoS σενάρια. Στη συνέχεια υλοποιήθηκαν παραλλαγές bandwidth broker που ακολουθούσαν κεντρικοποιημένες και κατανεμημένες αρχιτεκτονικές. Στόχος της μελέτης ήταν να μελετηθεί το trade-off στη λειτουργία τους και να συσχετιστεί με τις εκάστοτε δικτυακές συνθήκες. Στην κατανεμημένη λειτουργία εξαρτάται σημαντικά από την τοπολογία του δικτύου, από την διαμόρφωση του bandwidth broker πάνω στη τοπολογία και από την κατανομή QoS αιτημάτων. Για το τελευταίο μελετήθηκε ένας αλγόριθμος προσαρμογής ενός κατανεμημένου bandwidth broker ώστε να επιλέγεται η βέλτιστη διαμόρφωσή του στο δίκτυο (με βάση τις συνθήκες δικτύου) με στόχο την ταχύτερη απόκριση. Τέλος, στα πλαίσια της εργασίας αυτής διερευνήθηκε το θέμα της «inter domain» δρομολόγησης σε μια πλήρη τοπολογία ανεξάρτητων – αυτόνομων domains για την εξεύρεση του βέλτιστου μονοπατιού που ικανοποιεί τις QoS απαιτήσεις. Ειδικότερα , μελετήθηκαν διάφορα μοντέλα και δοκιμάστηκαν πειραματικά σε επίπεδο εξομοίωσης, δίνοντας έμφαση σε θέματα αυτονομίας διαχείρισης στο εσωτερικό κάθε ανεξάρτητου domain και στην τήρηση των SLAs μεταξύ γειτονικών domains.
Open Access
Ανάπτυξη συστημάτων δημοσιεύσεων/συνδρομών σε δομημένα δίκτυα ομοτίμων εταίρων
(2008-04-18T08:53:07Z) Αικατερινίδης, Ιωάννης; Τριανταφύλλου, Παναγιώτης; Τριανταφύλλου, Παναγιώτης; Βαρβαρίγος, Εμμανουήλ; Γαλλόπουλος, Ευστράτιος; Γαροφαλάκης, Ιωάννης; Κουμπαράκης, Εμμανουήλ; Πιτουρά, Ευαγγελία; Τσακαλίδης, Αθανάσιος; Aekaterinidis, Ioannis
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Τα τελευταία χρόνια οι εφαρμογές συνεχούς μετάδοσης ροών πληροφορίας στο διαδίκτυο έχουν γίνει ιδιαίτερα δημοφιλείς. Με τον συνεχώς αυξανόμενο ρυθμό εισόδου νέων αντικειμένων πληροφορίας, γίνεται ολοένα και πιο επιτακτική η ανάγκη για την ανάπτυξη πληροφορικών συστημάτων που να μπορούν να προσφέρουν στους χρήστες τους μόνο εκείνες τις πληροφορίες που τους ενδιαφέρουν, φιλτράροντας τεράστιους όγκους από άσχετες για τον κάθε χρήστη, πληροφορίες. Ένα μοντέλο διάδοσης πληροφορίας ικανό να ενσωματώσει τέτοιου είδους ιδιότητες, είναι το μοντέλο δημοσιεύσεων/συνδρομών βασισμένο στο περιεχόμενο ( content-based publish/subscribe) Βασική συνεισφορά μας στο χώρο είναι η εφαρμογή του μοντέλου δημοσιεύσεων/συνδρομών βασισμένου στο περιεχόμενο (content-based publish/subscribe) πάνω στα δίκτυα ομοτίμων ώστε να μπορέσουμε να προσφέρουμε στους χρήστες υψηλή εκφραστικότητα κατά την δήλωση των ενδιαφερόντων τους, λειτουργώντας σε ένα πλήρως κατανεμημένο και κλιμακώσιμο περιβάλλον. Ο κορμός των προτεινόμενων λύσεων σε αυτή τη διατριβή είναι: (α) η ανάπτυξη αλγορίθμων για την αποθήκευση των κλειδιών των δημοσιεύσεων σε κατάλληλους κόμβους του δικτύου με βάση τις συνθήκες στο περιεχόμενο που έχουν δηλωθεί και (β) αλγορίθμων δρομολόγησης δημοσιεύσεων στο διαδίκτυο έτσι ώστε να ((συναντούν)) αυτούς τους κόμβους οι οποίοι περιέχουν συνδρομές που ικανοποιούνται από την πληροφορία της δημοσίευσης. Οι προτεινόμενοι αλγόριθμοι υλοποιήθηκαν και εξετάσθηκαν ενδελεχώς με προσομοίωση μελετώντας την απόδοσή τους με βάση μετρικές όπως: η δίκαιη κατανομή του φόρτου στους κόμβους του δικτύου από τη διακίνηση μηνυμάτων κατά την επεξεργασία των συνδρομών/δημοσιεύσεων, ο συνολικός αριθμός μηνυμάτων που διακινούνται, ο συνολικός όγκος επιπλέον πληροφορίας που απαιτούν οι αλγόριθμοι να εισέλθει στο δίκτυο (network bandwidth), και ο χρόνος που απαιτείται για την ανεύρεση των συνδρομών που συζευγνύουν με κάθε δημοσίευση.
Open Access
Ασφαλή και έμπιστα πρωτόκολλα επικοινωνιών με χρήση κρυπτογραφίας και κρυπτανάλυσης
(2008-10-24T07:56:22Z) Λιάγκου, Βασιλική; Σπυράκης, Παύλος; Κακλαμάνης, Χρήστος; Σταματίου, Ιωάννης; Γαροφαλάκης, Ιωάννης; Καραγιάννης, Ιωάννης; Κυρούσης, Ελευθέριος; Νικολετσέας, Σωτήρης; Σπυράκης, Παύλος; Liagkou, Vasiliki
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Στην διδακτορική διατριβή αναπτύξαμε ασφαλή και έμπιστα πρωτόκολλα επικοινωνιών εισάγοντας ένα νέο μοντέλο έμπιστου συστήματος που ικανοποιεί τις συνεχώς εξελισσόμενες απαιτήσεις των υπολογιστικών συστημάτων. Για την ανάπτυξη του μοντέλου μας συνδυάσαμε την μαθηματική λογική και τα φαινόμενα κατωφλίου που προκύπτουν ασυμπτωτικά στην ανάπτυξη των συνδυαστικών δομών. Η βασική ιδέα της διδακτορικής διατριβής είναι ότι στα δυναμικά γενικά συστήματα υπολογισμού δεν μπορεί η έννοια της εμπιστοσύνης και της ασφάλειας να είναι στατική. Πιστεύουμε ότι ένα έμπιστο και ασφαλές σύστημα θα πρέπει να μελετάται με στατιστικές, ασυμπτωτικές παραμέτρους, καθώς τα τμήματα του συστήματος εξελίσσονται. Κατά συνέπεια, ο κύριος στόχος μας είναι να καθορίσουμε την εμπιστοσύνη ως μια ιδιότητα του συστήματος που «εμφανίζεται» όταν ισχύουν ασυμπωτικά, σχεδόν βέβαια ένα σύνολο λογικών ιδιοτήτων στις τυχαίες δομές επικοινωνίας, οι οποίες διαμορφώνουν τα συστήματα υπολογισμού. Στην διδακτορική διατριβή καθορίζονται διάφορες ιδιότητες που σχετίζονται με την ασφάλεια και εμπιστοσύνη του συστήματος και εκφράζονται χρησιμοποιώντας την λογική πρώτης ή δεύτερης τάξης και ταυτόχρονα ορίζονται και οι προϋποθέσεις κάτω από τις οποίες αυτές οι ιδιότητες εμφανίζονται στο όριο τους, καθώς το σύστημα αυξάνεται. Στην παρούσα εργασία χρησιμοποιούμε μοντέλα γράφων που μπορούν ρεαλιστικά να περιγράψουν ένα δυναμικό και συνεχώς εξελισσόμενο δίκτυο και δείχνουμε ότι αυτά τα μοντέλα μπορεί να χρησιμοποιηθούν για να ικανοποιούν διάφορες ``καλές'' ιδιότητες, οι οποίες του επιτρέπουν μια ασφαλή επικοινωνία. Το τελευταίο διάστημα παρουσιάζουν αρκετό ερευνητικό και επιστημονικό ενδιαφέρον τα ασύρματά δίκτυα που χρησιμοποιούν συσκευές με μικρούς πόρους σε μνήμη και ενέργεια. Επιπλέον η διδακτορική διατριβή περιλαμβάνει τον σχεδιασμό και την υλοποίηση νέων κρυπτογραφικών πρωτοκόλλων διαχείρισης κλειδιού σε τέτοια ασύρματα δυναμικά δίκτυα . Εδώ παρουσιάζουμε κρυπτογραφικά πρωτόκολλα που είναι κατάλληλα για μια μη στατική δομή δικτύου, τα οποία δεν απαιτούν συγκεκριμένη τοπολογία δικτύου και στηρίζονται μόνο στις απλές περιορισμένου φάσματος ανταλλαγές μηνυμάτων. Για να μπορέσουμε να αναπτύξουμε αυτά τα πρωτόκολλα βασιστήκαμε σε γνωστές κρυπταναλιτικές μεθόδους χρησιμοποιώντας πρωτόκολλα κρυπτογράφησης και αποκρυπτογράφησης. Τέλος η μελέτη μας δίνει έμφαση στα πλεονεκτήματα και τα μειονεκτήματα των πρωτοκόλλων μας δεδομένης της διαθέσιμης τεχνολογίας, των αντίστοιχων κριτηρίων αποδοτικότητας (ενέργεια, χρόνος) και του παρεχόμενου επιπέδου ασφάλειας.
Open Access
Ανάπτυξη αποδοτικών παραμετρικών τεχνικών αντιστοίχισης εικόνων με εφαρμογή στην υπολογιστική όραση
(2009-01-12T08:16:41Z) Ευαγγελίδης, Γεώργιος; Ψαράκης, Εμμανουήλ; Γαλατσάνος, Νικόλαος; Μουστακίδης, Γεώργιος; Μπερμπερίδης, Κωνσταντίνος; Φωτόπουλος, Σπυρίδων; Οικονόμου, Γεώργιος; Δερματάς, Ευάγγελος; Ψαράκης, Εμμανουήλ
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Μια από τις συνεχώς εξελισσόμενες περιοχές της επιστήμης των υπολογιστών είναι η Υπολογιστική Όραση, σκοπός της οποίας είναι η δημιουργία έξυπνων συστημάτων για την ανάκτηση πληροφοριών από πραγματικές εικόνες. Πολλές σύγχρονες εφαρμογές της υπολογιστικής όρασης βασίζονται στην αντιστοίχιση εικόνων. Την πλειοψηφία των αλγορίθμων αντιστοίχισης συνθέτουν παραμετρικές τεχνικές, σύμφωνα με τις οποίες υιοθετείται ένα παραμετρικό μοντέλο, το οποίο εφαρμοζόμενο στη μια εικόνα δύναται να παρέχει μια προσέγγιση της άλλης. Στο πλαίσιο της διατριβής μελετάται εκτενώς το πρόβλημα της Στερεοσκοπικής Αντιστοίχισης και το γενικό πρόβλημα της Ευθυγράμμισης Εικόνων. Για την αντιμετώπιση του πρώτου προβλήματος προτείνεται ένας τοπικός αλγόριθμος διαφορικής αντιστοίχισης που κάνει χρήση μιας νέας συνάρτησης κόστους, του Τροποποιημένου Συντελεστή Συσχέτισης (ECC), η οποία ενσωματώνει το παραμετρικό μοντέλο μετατόπισης στον κλασικό συντελεστή συσχέτισης. Η ενσωμάτωση αυτή καθιστά τη νέα συνάρτηση κατάλληλη για εκτιμήσεις ανομοιότητας με ακρίβεια μικρότερη από αυτήν του εικονοστοιχείου. Αν και η συνάρτηση αυτή είναι μη γραμμική ως προς την παράμετρο μετατόπισης, το πρόβλημα μεγιστοποίησης έχει κλειστού τύπου λύση με αποτέλεσμα τη μειωμένη πολυπλοκότητα της διαδικασίας της αντιστοίχισης με ακρίβεια υπο-εικονοστοιχείου. Ο προτεινόμενος αλγόριθμος παρέχει ακριβή αποτελέσματα ακόμα και κάτω από μη γραμμικές φωτομετρικές παραμορφώσεις, ενώ η απόδοσή του υπερτερεί έναντι γνωστών στη διεθνή βιβλιογραφία τεχνικών αντιστοίχισης ενώ φαίνεται να είναι απαλλαγμένος από το φαινόμενο pixel locking. Στην περίπτωση του προβλήματος της ευθυγράμμισης εικόνων, η προτεινόμενη συνάρτηση γενικεύεται με αποτέλεσμα τη δυνατότητα χρήσης οποιουδήποτε δισδιάστατου μετασχηματισμού. Η μεγιστοποίησή της, η οποία αποτελεί ένα μη γραμμικό πρόβλημα, επιτυγχάνεται μέσω της επίλυσης μιας ακολουθίας υπο-προβλημάτων βελτιστοποίησης. Σε κάθε επανάληψη επιβάλλεται η μεγιστοποίηση μιας μη γραμμικής συνάρτησης του διανύσματος διορθώσεων των παραμέτρων, η οποία αποδεικνύεται ότι καταλήγει στη λύση ενός γραμμικού συστήματος. Δύο εκδόσεις του σχήματος αυτού προτείνονται: ο αλγόριθμος Forwards Additive ECC (FA-ECC) και o αποδοτικός υπολογιστικά αλγόριθμος Inverse Compositional ECC (IC-ECC). Τα προτεινόμενα σχήματα συγκρίνονται με τα αντίστοιχα (FA-LK και SIC) του αλγόριθμου Lucas-Kanade, ο οποίος αποτελεί σημείο αναφοράς στη σχετική βιβλιογραφία, μέσα από μια σειρά πειραμάτων. Ο αλγόριθμος FA-ECC παρουσιάζει όμοια πολυπλοκότητα με τον ευρέως χρησιμοποιούμενο αλγόριθμο FA-LΚ και παρέχει πιο ακριβή αποτελέσματα ενώ συγκλίνει με αισθητά μεγαλύτερη πιθανότητα και ταχύτητα. Παράλληλα, παρουσιάζεται πιο εύρωστος σε περιπτώσεις παρουσίας προσθετικού θορύβου, φωτομετρικών παραμορφώσεων και υπερ-μοντελοποίησης της γεωμετρικής παραμόρφωσης των εικόνων. Ο αλγόριθμος IC-ECC κάνει χρήση της αντίστροφης λογικής, η οποία στηρίζεται στην αλλαγή των ρόλων των εικόνων αντιστοίχισης και συνδυάζει τον κανόνα ενημέρωσης των παραμέτρων μέσω της σύνθεσης των μετασχηματισμών. Τα δύο αυτά χαρακτηριστικά έχουν ως αποτέλεσμα τη δραστική μείωση του υπολογιστικού κόστους, ακόμα και σε σχέση με τον SIC αλγόριθμο, με τον οποίο βέβαια παρουσιάζει παρόμοια συμπεριφορά. Αν και ο αλγόριθμος FA-ECC γενικά υπερτερεί έναντι των τριών άλλων αλγορίθμων, η επιλογή μεταξύ των δύο προτεινόμενων σχημάτων εξαρτάται από το λόγο μεταξύ ακρίβειας αντιστοίχισης και υπολογιστικού κόστους.
Open Access
Επεξεργασία πολύπλοκων ερωτημάτων και εκτίμηση ανομοιόμορφων κατανομών σε κατανεμημένα δίκτυα κλίμακας ίντερνετ
(2009-01-12T10:13:20Z) Πιτουρά, Θεώνη; Τριανταφύλλου, Παναγιώτης; Βαζιργιάννης, Μιχάλης; Γαλλόπουλος, Ευστράτιος; Ζαρολιάγκης, Χρήστος; Κουμπαράκης, Μανόλης; Σπυράκης, Παύλος; Τριανταφύλλου, Παναγιώτης; Τσακαλίδης, Αθανάσιος; Pitoura, Theoni
Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)
Τα κατανεμημένα δίκτυα κλίμακας Ίντερνετ και κυρίως τα δίκτυα ομοτίμων εταίρων, γνωστά και ως peer-to-peer (p2p), που αποτελούν το πιο αντιπροσωπευτικό παράδειγμά τους, προσελκύουν τα τελευταία χρόνια μεγάλο ενδιαφέρον από τους ερευνητές και τις επιχειρήσεις λόγω των ιδιόμορφων χαρακτηριστικών τους, όπως ο πλήρης αποκεντρωτικός χαρακτήρας, η αυτονομία των κόμβων, η ικανότητα κλιμάκωσης, κ.λπ. Αρχικά σχεδιασμένα να υποστηρίζουν εφαρμογές διαμοιρασμού αρχείων με βασική υπηρεσία την επεξεργασία απλών ερωτημάτων, σύντομα εξελίχτηκαν σε ένα καινούργιο μοντέλο κατανεμημένων συστημάτων, με μεγάλες και αυξανόμενες δυνατότητες για διαδικτυακές εφαρμογές, υποστηρίζοντας πολύπλοκες εφαρμογές διαμοιρασμού δομημένων και σημασιολογικά προσδιορισμένων δεδομένων. Η προσέγγισή μας στην περιοχή αυτή γίνεται προς δύο βασικές κατευθύνσεις: (α) την επεξεργασία πολύπλοκων ερωτημάτων και (β) την εκτίμηση των ανομοιομορφιών των διαφόρων κατανομών που συναντάμε στα δίκτυα αυτά (π.χ. φορτίου, προσφοράς ή κατανάλωσης ενός πόρου, τιμών των δεδομένων των κόμβων, κ.λπ.), που εκτός των άλλων αποτελεί ένα σημαντικό εργαλείο στην υποστήριξη πολύπλοκων ερωτημάτων. Συγκεκριμένα, ασχολούμαστε και επιλύουμε τρία βασικά ανοικτά προβλήματα. Το πρώτο ανοικτό πρόβλημα είναι η επεξεργασία ερωτημάτων εύρους τιμών σε ομότιμα συστήματα κατανεμημένου πίνακα κατακερματισμού, με ταυτόχρονη εξασφάλιση της εξισορρόπησης του φορτίου των κόμβων και της ανοχής σε σφάλματα. Προτείνουμε μια αρχιτεκτονική επικάλυψης, που ονομάζουμε Saturn, που εφαρμόζεται πάνω από ένα δίκτυο κατανεμημένου πίνακα κατακερματισμού. Η αρχιτεκτονική Saturn χρησιμοποιεί: (α) μια πρωτότυπη συνάρτηση κατακερματισμού που τοποθετεί διαδοχικές τιμές δεδομένων σε γειτονικούς κόμβους, για την αποδοτική επεξεργασία των ερωτημάτων εύρους τιμών και (β) την αντιγραφή, για την εξασφάλιση της εξισορρόπησης του φορτίου προσπελάσεων (κάθετη, καθοδηγούμενη από το φορτίο αντιγραφή) και της ανοχής σε σφάλματα (οριζόντια αντιγραφή). Μέσα από μια εκτεταμένη πειραματική αξιολόγηση του Saturn και σύγκριση με δύο βασικά δίκτυα κατανεμημένου πίνακα κατακερματισμού (Chord και OP-Chord) πιστοποιούμε την ανωτερότητα του Saturn να αντιμετωπίζει και τα τρία ζητήματα που θέσαμε, αλλά και την ικανότητά του να συντονίζει το βαθμό αντιγραφής ώστε να ανταλλάζει ανάμεσα στο κόστος αντιγραφής και στο βαθμό εξισορρόπησης του φορτίου. Το δεύτερο ανοικτό πρόβλημα που αντιμετωπίζουμε αφορά την έλλειψη κατάλληλων μετρικών που να εκφράζουν τις ανομοιομορφίες των διαφόρων κατανομών (όπως, για παράδειγμα, το βαθμό δικαιοσύνης μιας κατανομής φορτίου) σε κατανεμημένα δίκτυα κλίμακας Ίντερνετ και την μη αποτελεσματική ή δυναμική εκμετάλλευση μετρικών ανομοιομορφίας σε συνδυασμό με αλγορίθμους διόρθωσης (όπως ο αλγόριθμος εξισορρόπησης φορτίου). Το πρόβλημα είναι σημαντικό γιατί η εκτίμηση των κατανομών συντελεί στην ικανότητα κλιμάκωσης και στην επίδοση αυτών των δικτύων. Αρχικά, προτείνουμε τρεις μετρικές ανομοιομορφίας (το συντελεστή του Gini, τον δείκτη δικαιοσύνης και το συντελεστή διασποράς) μετά από μια αναλυτική αξιολόγηση μεταξύ γνωστών μετρικών εκτίμησης ανομοιομορφίας και στη συνέχεια, αναπτύσσουμε τεχνικές δειγματοληψίας (τρεις γνωστές τεχνικές και τρεις προτεινόμενες) για τη δυναμική εκτίμηση αυτών των μετρικών. Με εκτεταμένα πειράματα αξιολογούμε συγκριτικά τους προτεινόμενους αλγορίθμους εκτίμησης και τις τρεις μετρικές και επιδεικνύουμε πώς αυτές οι μετρικές και ειδικά, ο συντελεστής του Gini, μπορούν να χρησιμοποιηθούν εύκολα και δυναμικά από υψηλότερου επιπέδου αλγορίθμους, οι οποίοι μπορούν τώρα να ξέρουν πότε να επέμβουν για να διορθώσουν τις άδικες κατανομές. Το τρίτο και τελευταίο ανοικτό πρόβλημα αφορά την εκτίμηση του μεγέθους αυτοσύνδεσης μιας σχέσης όπου οι πλειάδες της είναι κατανεμημένες σε κόμβους δεδομένων που αποτελούν ένα ομότιμο δίκτυο επικάλυψης. Το μέγεθος αυτοσύνδεσης έχει χρησιμοποιηθεί εκτεταμένα σε συγκεντρωτικές βάσεις δεδομένων για τη βελτιστοποίηση ερωτημάτων και υποστηρίζουμε ότι μπορεί να χρησιμοποιηθεί και σε ένα πλήθος άλλων εφαρμογών, ειδικά στα ομότιμα δίκτυα (π.χ. συσταδοποίηση του Ιστού, αναζήτηση στον Ιστό, κ.λπ.). Η συνεισφορά μας περιλαμβάνει, αρχικά, τις προσαρμογές πέντε γνωστών συγκεντρωτικών τεχνικών εκτίμησης του μεγέθους αυτοσύνδεσης (συγκεκριμένα, σειριακή, ετεροδειγματοληπτική, προσαρμοστική και διεστιακή δειγματοληψία και δειγματοληψία με μέτρηση δείγματος) στο περιβάλλον ομοτίμων εταίρων και η ανάπτυξη μια πρωτότυπης τεχνικής εκτίμησης του μεγέθους αυτοσύνδεσης, βασισμένη στο συντελεστή του Gini. Με μαθηματική ανάλυση δείχνουμε ότι οι εκτιμήσεις του συντελεστή του Gini μπορούν να οδηγήσουν σε εκτιμήσεις των υποκείμενων κατανομών δεδομένων, όταν αυτά ακολουθούν το νόμο της δύναμης ή το νόμο του Zipf και αυτές, με τη σειρά τους, σε εκτιμήσεις του μεγέθους αυτοσύνδεσης των σχέσεων των δεδομένων. Μετά από αναλυτική πειραματική μελέτη και σύγκριση όλων των παραπάνω τεχνικών αποδεικνύουμε ότι η καινούργια τεχνική που προτείνουμε είναι πολύ αποτελεσματική ως προς την ακρίβεια, την πιστότητα και την απόδοση έναντι των άλλων πέντε μεθόδων.