Θέμα της παρούσης διπλωματικής εργασίας αποτελεί η μελέτη, ανάπτυξη και πειραματική επιβεβαίωση αλγοριθμικών τεχνικών για την σχεδίαση αυτοοργανώμενων δομών δεδομένων (self-organizing data structures) και η ανάπτυξη τυχαιοποιημένων εκδόσεών τους. Μια αυτοοργανώμενη δομή δεδομένων διαθέτει κάποιον αλγόριθμο για να αναδιοργανώνει τους δείκτες και τα δεδομένα κατάστασης μετά από κάθε πρόσβαση ή πράξη . Ο αλγόριθμος αυτοοργάνωσης είναι σχεδιασμένος ώστε αντιδρώντας σε αρχικά άγνωστες ιδιότητες της ακολουθίας αιτήσεων (request sequence), να οδηγεί τη δομή δεδομένων σε κατάσταση πλεονεκτική για τις ιδιότητες της ακολουθίας με αποτέλεσμα τη μείωση του χρόνου που χρειάζεται στο μέλλον ανά πράξη. Ο πρώτος αλλά και ο μόνος μέχρι σήμερα πιθανός υποψήφιος αλγόριθμος αναζήτησης σε δένδρο που μπορεί να είναι Ο(1)-ανταγωνιστικός είναι το splay δένδρο (splay tree) που παρουσιάστηκε από τους Sleator και Tarjan [1]. Στην εργασία των Sleator και Tarjan παρουσιάζονται κάποιες εικασίες, οι οποίες δεν έχουν αποδειχθεί. Σημαντικότερη είναι η εικασία δυναμικής βελτιστότητας (dynamic optimality conjecture) σύμφωνα με την οποία το splay δένδρο είναι Ο(1)-ανταγωνιστικό. Η εικασία δυναμικής δακτυλοδότησης (dynamic finger conjecture) και η εικασία διαπέρασης (traversal conjecture) είναι αληθείς, αν είναι αληθής η εικασία δυναμικής βελτιστότητας. Ο Cole [3], [4] προσπάθησε να αποδείξει την ορθότητα της εικασίας δυναμικής δακτυλοδότησης σε μια από τις σημαντικότερες εργασίες για τα splay δένδρα. O J. Iacono [2] ανέπτυξε εναλλακτικές δομές δεδομένων που έχουν χρόνο χειρότερης περίπτωσης ανά πράξη (και όχι επιμερισμένο κόστος) της τάξης του Ο(logn), σε αντιδιαστολή με τον Ο(n) χρόνο χειρότερης περίπτωσης των splay trees. Σε αντιπαράθεση με τη δομή του Iacono, οι Mihai Badoiu και Erik D. Demaine παρουσίασαν μια δυναμική δομή αναζήτησης[7], η οποία επιτυγχάνει την ενοποιημένη ιδιότητα και που είναι απλούστερη από τη δομή του Iacono. Μεταξύ όλων των δυναμικών δομών αναζήτησης με βάση τις συγκρίσεις , η συγκεκριμένη δομή έχει τον καλύτερο χρόνο εκτέλεσης. Εκτός της παραπάνω δομής, ο Demaine ανέπτυξε ένα Ο(loglogn) ανταγωνιστικό online δυαδικό δέντρο αναζήτησης[5] , βελτιώνοντας το μέχρι πρότινος βέλτιστο ανταγωνιστικό ποσοστό της τάξης Ο(logn). Αυτή είναι η πρώτη μεγάλη βελτίωση της εικασίας δυναμικής βελτιστότητας (dynamic optimality conjecture) των Sleator και Tarjan , σύμφωνα με την οποία υπάρχουν Ο(1) ανταγωνιστικά δυαδικά δέντρα αναζήτησης. Σε σχέση με τη δυναμική βελτιστότητα των Splay trees, σημαντική συνεισφορά αποτελεί και η εργασία του George F. Georgakopoulos[6]. Ο George F. Georgakopoulos παρουσιάζει μια επέκταση της splay τεχνικής , την οποία ονομάζει chain-splay(αλυσιδωτό splay) . Τα chain-splay δέντρα εφαρμόζουν splay στο στοιχείο που προσπελαύνουμε προς τη ρίζα όπως ακριβώς γίνεται και στα κλασικά splay trees, αλλά εκτελούν και μερικές τοπικές splay πράξεις τακτοποίησης κάτω από το στοιχείο που προσπελάσαμε. Αποδεικνύεται πως η τεχνική chain–splay είναι Ο(loglogn) ανταγωνιστική σε σχέση με οποιοδήποτε offline αλγόριθμο αναζήτησης. Tέλος, ο George F. Georgakopoulos [9] έδωσε ένα νέο λήμμα επαναζύγισης για τα splay δέντρα και με βάση αυτό το λήμμα, αποδεικνύει πως τα splay δέντρα είναι ανταγωνιστικά προς κάθε κλάση δυναμικών ισοζυγισμένων δέντρων. Οι παραπάνω δομές θα μελετηθούν τόσο σε θεωρητικό όσο και σε πειραματικό επίπεδο με σκοπό την εξαγωγή χρήσιμων συμπερασμάτων σε σχέση με την αποδοτικότητά τους αλλά και με σκοπό την καταγραφή των ακόμη ανοικτών προβλημάτων και των προοπτικών επίλυσης τους. Επιπλέον, θα παρουσιαστούν τυχαιοποιημένες εκδόσεις των δομών των Demaine και Georgakopoulos. Οι δομές αυτές θα υλοποιηθούν και η απόδοσή τους θα τεκμηριωθεί τόσο πειραματικά όσο και θεωρητικά. Σημαντικής σημασίας είναι η σύγκρισή τους με τις αρχικές δομές, ώστε να εξαχθούν συμπεράσματα σχετικά με την συμβολή της τυχαιοποίησης στη βελτίωση της απόδοσης των δομών. / -

Οι κινητικές δομές δεδομένων KDSs (kinetic data structures) είναι ένα νέο πλαίσιο εργασίας για το σχεδιασμό και την ανάλυση αλγορίθμων σχετικών με γεωμε- τρικά αντικείμενα (ευθύγραμμα τμήματα, πολύγωνα, δίσκοι κ.τ.λ.) σε κίνηση. Σκο- πός μας είναι να διατηρήσουμε ένα χαρακτηριστικό ενός συνόλου κινούμενων αντι- κειμένων, π.χ. την κυρτή θήκη ή το κοντινότερο ζευγάρι του. Η διατήρηση του χαρα κτηριστικού γίνεται μέσω ενός συνόλου συνθηκών που εγγυώνται την εγκυρότητα της δομής κάθε χρονική στιγμή και το οποίο μεταβάλλεται με το χρόνο λόγω της κίνησης. Οι συνθήκες αποθηκεύονται σε μια ουρά διατεταγμένες χρονολογικά. Κάθε φορά που αλλάζει το χαρακτηριστικό που μας ενδιαφέρει ενημερώνουμε τη δομή μας και την ουρά. Η πρώτη ενότητα της εργασίας είναι μια εισαγωγή στις KDSs. Αναφέρουμε βασικές έννοιες και ιδέες των KDSs όπως: συνάρτηση διαμόρφωσης, πιστοποιητικά, κρίσιμα γεγονότα. Επίσης, ασχολούμαστε και με τα μέτρα απόδοσής τους. Στη δεύτερη ενότητα ασχολούμαστε με τους δυαδικούς διαχωρισμούς χώρου BSPs, πρώτα σε στατικό και κατόπιν σε κινητικό περιβάλλον. Συγκεκριμένα παρουσιάζουμε τρεις αλγορίθμους για τη διατήρηση του BSP ενός συνόλου κινούμενων ευθυγράμμων τμημάτων στο επίπεδο. Σύμφωνα με τον πρώτο γνωστό αλγόριθμο που διατυπώθηκε για την αποτελεσματική διατήρηση του BSP για ένα σύνολο μη-τεμνόμενων ευθυγράμμων τμημάτων S στο επίπεδο χρησιμοποιώντας τη φιλοσοφία των KDSs, κατασκευάζουμε έναν BSP για το S θεωρώντας τα ευθύγραμμα τμήματα στάσιμα και στη συνέχεια τον διατηρούμε καθώς αυτά κινούνται. Ο δεύτερος αλγόριθμος είναι ουσιαστικά μια επέκταση του πρώτου καθώς ασχολείται με το ίδιο πρόβλημα, αλλά για τεμνόμενα ευθύγραμμα τμήματα. Αλλάζει το σύνολο των πιστοποιητικών και οι τρόποι με τους οποίους μπορεί να αλλάξει η δομή του BSP. Ο τρίτος αλγόριθμος χρησιμοποιεί ένα διαφορετικό τρόπο για την κατασκευή και διατήρηση του BSP για το σύνολο S βελτιώνοντας τον αρχικό. Στην τρίτη ενότητα ασχολούμαστε με τη διατήρηση του Voronoi διαγράμματος (VD) για ένα σύνολο κινούμενων, πιθανώς τεμνόμενων δίσκων στο επίπεδο και του συμπαγούς Voronoi διαγράμματος για ένα σύνολο μη-τεμνόμενων κυρτών πολυγώνων στο επίπεδο (το συμπαγές VD είναι δυϊκό του VD, αλλά το μέγεθός του είναι συνάρτηση του αριθμού των πολυγώνων και όχι του αριθμού των κορυφών). Και στις δύο περιπτώσεις, η επίλυση του προβλήματος ανάγεται στη διατήρηση του δυϊκού του VD, της τριγωνοποίησης Delaunay DT . Η διατήρηση της DT βασίζεται στο γεγονός ότι ένα σύνολο τοπικών συνθηκών (έλεγχοι InCircle), πιστοποιούν την ολική ορθότητα της δομής και τοπικές επιδιορθώσεις είναι πάντα εφικτές. Έτσι, καθώς τα αντικείμενα κινούνται, έχουμε κάθε στιγμή μια έγκυρη DT και συνεπώς ένα έγκυρο VD. Τέλος, αναφέρουμε μια KDS για τον εντοπισμό συγκρούσεων μεταξύ δύο απλών πολυγώνων σε κίνηση. Ο αλγόριθμος διατηρεί μια υποδιαίρεση του ελεύθερου χώρου μεταξύ των πολυγώνων, που καλείται external relative geodesic triangulation, η οποία πιστοποιεί τη μη-σύγκρουσή των πολυγώνων. / Kinetic Data Structures (KDSs) are a new framework for designing and analyzing algorithms for geometrics objects (segments, polygons, disks etc.) in motion. Our goal is to maintain an attribute of a set of moving objects, for example the convex hull or the closest pair. The maintenance of the attribute is made through a set of conditions that guarantee the validity of the structure every moment. This set is changed with time due to the motion. The conditions are stored in a queue ordered chronologically. Every time the attribute is changed, we update the structure and the queue. The first chapter is an introduction to the KDSs. We mention basic notions and ideas of the KDSs, like: configuration function, certificates, critical events. Furthermore, we discuss their measure of performance. In the second chapter we deal with the Binary Space Partitions (BSPs), first in static and then in kinetic environment. Specifically, we present three algorithms for the maintenance of a BSP for a set of moving segments in the plane. According to the first known algorithm which was proposed for efficiently maintaining the BSP for a set of non-intersecting segments S in the plane using the philosophy of KDSs, we construct a BSP - considering that the segments are static - and then we maintain it as the segments move. The second algorithm is substantially an expansion of the first algorithm as it deals with the same problem, but for intersecting segments. The set of the certificates is changed as well as the set of critical events. The third algorithm uses a different technique for the construction and maintenance of the BSP for the set S. It is an improvement of the first algorithm. In the third chapter, we deal with the maintenance of the Voronoi diagram (VD) for a set of moving, probably intersecting disks in the plane and the maintenance of a compact Voronoi-like diagram for a set of non-intersecting, convex polygons in the plane (compact VD is dual to VD, except that its size is a function of the number of polygons and not of the number of vertices). In both cases, we solve the problem by maintaining the dual graph of VD, the Delaunay triangulation (DT ). The maintenance of the DT is based in the fact that a set of local conditions (InCircle tests) guarantee the total correctness of the structure and we are able to do only local changes. So, as the objects move, we have a valid DT every moment and consequently a valid VD. Finally, we mention a KDS for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the polygons, called External Relative Geodesic Triangulation, which certify their disjointness.

Αντικείμενο της παρούσας διδακτορικής διατριβής είναι η μελέτη και τροποποίηση βασικών δομών δεδομένων με σκοπό τη δημιουργία νέων και την τροποποίηση υπαρχουσών λύσεων, με εφαρμογές στην Ανάκτηση Πληροφορίας, τη Βιοπληροφορική και το Διαδίκτυο. Αρχικά, δίνεται έμφαση στην ανάπτυξη και πειραματική επιβεβαίωση αλγοριθμικών τεχνικών για τη σχεδίαση αυτοοργανώμενων δομών δεδομένων (self-organizing data structures). Μέχρι σήμερα, ο μόνος πιθανός υποψήφιος αλγόριθμος αναζήτησης σε δένδρο που μπορεί να είναι Ο(1)-ανταγωνιστικός είναι το splay δένδρο (splay tree) που παρουσιάστηκε από τους Sleator και Tarjan [1]. Επιπρόσθετα, μελετώνται διάφορες εναλλακτικές τεχνικές αυτοοργάνωσης ([2],[3],[4],[5],[6]) και γίνεται επιβεβαίωση των πάνω ορίων που ισχύουν για την απόδοση των splay trees και για αυτές. Η ανάπτυξη των διάφορων αλγοριθμικών αυτών τεχνικών βρίσκει εφαρμογές πάνω στη συμπίεση δεδομένων. Οι αλγόριθμοι συμπίεσης δεδομένων μπορούν να βελτιώσουν την αποδοτικότητα με την οποία τα δεδομένα αποθηκεύονται ή μεταφέρονται, μέσω της μείωσης του ποσού της πλεονάζουσας πληροφορίας. Η χρήση αυτών των αλγορίθμων τόσο στην κρυπτογράφηση όσο και στην επεξεργασία εικόνας είναι αποδοτική και έχει μεγάλο ερευνητικό ενδιαφέρον. Γενικότερα, οι αυτοοργανώμενες δομές δεδομένων χρίζουν ιδιαίτερης προσοχής στους on-line αλγόριθμους. Αναλυτικότερα, στην παρούσα διατριβή, εφαρμόζεται συμπίεση σε βιολογικά δεδομένα αλλά και σε κείμενα τόσο με χρήση του κλασσικού splay δέντρου [10] αλλά και της log log n ανταγωνιστικής παραλλαγής του. Επιπλέον, παρουσιάζονται τυχαιοποιημένες εκδόσεις των παραπάνω δομών και εφαρμόζονται και αυτές στη συμπίεση δεδομένων. Οι log log n ανταγωνιστικές δομές έχουν καλύτερη απόδοση όσον αφορά την πολυπλοκότητά τους σε σχέση με την κλασσική splay δομή. Το γεγονός αυτό επιβεβαιώνεται πειραματικά, όπου η επιτυγχανόμενη συμπίεση είναι στις περισσότερες των περιπτώσεων καλύτερη από την αντίστοιχη της κλασικής δομής . Επιπλέον, ιδιαίτερο ερευνητικό ενδιαφέρον βρίσκει η εφαρμογή βασικών δομών δεδομένων στο διαδίκτυο. Επιδιώκουμε την ανάπτυξη και θεωρητική επιβεβαίωση αλγορίθμων για προβλήματα όπως η ανάθεση «καυτών συνδέσμων» (hot links [7]), η αναδιοργάνωση ιστοσελίδων και η ανάκτηση πληροφορίας ([8],[9]). Σε πρώτο στάδιο, προτείνονται ευριστικοί αλγόριθμοι με σκοπό την ανάθεση «καυτών συνδέσμων» (hotlinks) και τη βελτίωση της τοπολογίας ενός ιστότοπου ([12],[13],[14]). Σκοπός του αλγορίθμου είναι η προώθηση των δημοφιλών ιστοσελίδων ενός ιστότοπου, μέσω της ανάθεσης συνδέσμων προς αυτές, από ιστοσελίδες οι οποίες είναι σχετικές με αυτές ως προς το περιεχόμενο αλλά και ταυτόχρονα συντελούν στη μείωση της απόστασής τους από την αρχική σελίδα. Παρουσιάζεται το μοντέλο του αλγορίθμου, καθώς και μετρικές οι οποίες χρησιμοποιούνται για την ποσοτική αξιολόγηση της αποδοτικότητας του αλγορίθμου σε σχέση με ειδικά χαρακτηριστικά ενός ιστότοπου, όπως η εντροπία του. Σε δεύτερο στάδιο, γίνεται μελέτη τεχνικών προσωποποίησης ιστοσελίδων [11]. Συγκεκριμένα, σκοπός είναι η υλοποίηση ενός αλγορίθμου, ο οποίος θα ανακαλύπτει την αυξημένη ζήτηση μίας κατηγορίας ιστοσελίδων Α από έναν χρήστη και αξιοποιώντας την καταγεγραμμένη συμπεριφορά άλλων χρηστών, θα προτείνει κατηγορίες σελίδων οι οποίες προτιμήθηκαν από χρήστες οι οποίοι ομοίως παρουσίασαν αυξημένο ενδιαφέρον προς την κατηγορία αυτή. Αναλύεται το φαινόμενο της έξαρσης επισκεψιμότητας (burst) και η αξιοποίηση του στο πεδίο της εξατομίκευσης ιστοσελίδων. Ο αλγόριθμος υλοποιείται με τη χρήση δύο δομών δεδομένων, των Binary heaps και των Splay δέντρων, και αναλύεται η χρονική και χωρική πολυπλοκότητά του. Επιπρόσθετα, γίνεται πειραματική επιβεβαίωση της ορθής και αποδοτικής εκτέλεσης του αλγορίθμου. Αξίζει να σημειωθεί πως ο προτεινόμενος αλγόριθμος λόγω της φύσης του, χρησιμοποιεί χώρο, ο οποίος επιτρέπει τη χρησιμοποίηση του στη RAM. Τέλος, ο προτεινόμενος αλγόριθμος δύναται να βρει εφαρμογή σε εξατομίκευση σελίδων με βάση το σημασιολογικό τους περιεχόμενο σε αντιστοιχία με το διαχωρισμό τους σε κατηγορίες. Σε τρίτο στάδιο, γίνεται παρουσίαση πρωτότυπης τεχνικής σύστασης ιστοσελίδων [15] με χρήση Splay δέντρων. Σε αυτή την περίπτωση, δίνεται ιδιαίτερο βάρος στην εύρεση των σελίδων που παρουσιάζουν έξαρση επισκεψιμότητας και στη σύστασή τους στους χρήστες ενός ιστότοπου. Αρχικά, τεκμηριώνεται η αξία της εύρεσης μιας σελίδας, η οποία δέχεται ένα burst επισκέψεων. H έξαρση επισκεψιμότητας (burst) ορίζεται σε σχέση τόσο με τον αριθμό των επισκέψεων, όσο και με το χρονικό διάστημα επιτέλεσής τους. Η εύρεση των σελίδων επιτυγχάνεται με τη μοντελοποίηση ενός ιστότοπου μέσω ενός splay δέντρου. Με την τροποποίηση του δέντρου μέσω της χρήσης χρονοσφραγίδων (timestamps), ο αλγόριθμος είναι σε θέση να επιστρέφει σε κάθε χρονική στιγμή την ιστοσελίδα που έχει δεχθεί το πιο πρόσφατο burst επισκέψεων. Ο αλγόριθμος αναλύεται όσον αφορά τη χωρική και χρονική του πολυπλοκότητα και συγκρίνεται με εναλλακτικές λύσεις. Μείζονος σημασίας είναι η δυνατότητα εφαρμογής του αλγορίθμου και σε άλλα φαινόμενα της καθημερινότητας μέσω της ανάλογης μοντελοποίησης. Παραδείγματος χάρη, στην περίπτωση της απεικόνισης ενός συγκοινωνιακού δικτύου μέσω ενός γράφου, ο αλγόριθμος σύστασης δύναται να επιστρέφει σε κάθε περίπτωση τον κυκλοφοριακό κόμβο ο οποίος παρουσιάζει την πιο πρόσφατη συμφόρηση. Τέλος, όσον αφορά το πεδίο της ανάκτησης πληροφορίας, η διατριβή επικεντρώνεται σε μία πρωτότυπη και ολοκληρωμένη μεθοδολογία με σκοπό την αξιολόγηση της ποιότητας ενός συστήματος λογισμικού βάσει του Προτύπου Ποιότητας ISO/IEC-9126. Το κύριο χαρακτηριστικό της είναι ότι ολοκληρώνει την αξιολόγηση ενός συστήματος λογισμικού ενσωματώνοντας την αποτίμηση όχι μόνο των χαρακτηριστικών που είναι προσανατολισμένα στο χρήστη, αλλά και εκείνων που είναι πιο τεχνικά και αφορούν τους μηχανικούς λογισμικού ενός συστήματος. Σε αυτή τη διατριβή δίνεται βάρος στην εφαρμογή μεθόδων εξόρυξης δεδομένων πάνω στα αποτελέσματα της μέτρησης μετρικών οι οποίες συνθέτουν τα χαρακτηριστικά του πηγαίου κώδικα, όπως αυτά ορίζονται από το Προτύπο Ποιότητας ISO/IEC-9126 [16][17]. Ειδικότερα εφαρμόζονται αλγόριθμοι συσταδοποίησης με σκοπό την εύρεση τμημάτων κώδικα με ιδιαίτερα χαρακτηριστικά, που χρήζουν προσοχής. / In this dissertation we take an in-depth look at the use of effective and efficient data structures and algorithms in the fields of data mining and web technologies. The main goal is to develop algorithms based on appropriate data structures, in order to improve the performance at all levels of web applications. In the first chapter the reader is introduced to the main issues studied dissertation. In the second chapter, we propose novel randomized versions of the splay trees. We have evaluated the practical performance of these structures in comparison with the original version of splay trees and with their log log n-competitive variations, in the application field of compression. Moreover, we show that the Chain Splay tree achieves O(logn) worst-case cost per query. In order to evaluate performance, we utilize plain splay trees, the log log n-competitive variations, the proposed randomized version with the Chain Splay technique to compress data. It is observed experimentally that the compression achieved in the case of the log log n-competitive technique is, as expected, more efficient than the one of the plain splay trees. The third chapter focuses on hotlinks assignment techniques. Enhancing web browsing experience is an open issue frequently dealt using hotlinks assignment between webpages, shortcuts from one node to another. Our aim is to provide a novel, more efficient approach to minimize the expected number of steps needed to reach expected pages when browsing a website. We present a randomized algorithm, which combines the popularity of the webpages, the website structure, and for the first time to the best authors’ knowledge, the similarity of context between pages in order to suggest the placement of suitable hotlinks. We verify experimentally that users need less page transitions to reach expected information pages when browsing a website, enhanced using the proposed algorithm. In the fourth chapter we investigate the problem of web personalization. The explosive growth in the size and use of the World Wide Web continuously creates new great challenges and needs. The need for predicting the users’ preferences in order to expedite and improve the browsing though a site can be achieved through personalizing of the Websites. Recommendation and personalization algorithms aim at suggesting WebPages to users based on their current visit and past users’ navigational patterns. The problem that we address is the case where few WebPages become very popular for short periods of time and are accessed very frequently in a limited temporal space. Our aim is to deal with these bursts of visits and suggest these highly accessed pages to the future users that have common interests. Hence, in this paper, we propose a new web personalization technique, based on advanced data structures. The data structures that are used are the Splay tree (1) and Binary heaps (2). We describe the architecture of the technique, analyze the time and space complexity and prove its performance. In addition, we compare both theoretically and experimentally the proposed technique to another approach to verify its efficiency. Our solution achieves O(P2) space complexity and runs in k log P time, where k is the number of pages and P the number of categories of WebPages. Extending this algorithm, we propose an algorithm which efficiently detects bursts of visits to webpages. As an increasing number of Web sites consist of multiple pages, it is more difficult for the visitors to rapidly reach their own target. This results in an urgent need for intelligent systems that effectively support the users’ navigation to high demand Web content. In many cases, due to specific conditions, web pages become very popular and receive excessively large number of hits. Therefore, there is a high probability that these web pages will be of interest to the majority of the visitors at a given time. The data structure that is used for the purposes of the recommendation algorithm is the Splay tree. We describe the architecture of the technique, analyze the time and space complexity and show its performance. The dissertation’s last chapter elaborates on how to use clustering for the evaluation of a software system’s maintainability according to the ISO/IEC-9126 quality standard. More specifically it proposes a methodology that combines clustering and multicriteria decision aid techniques for knowledge acquisition by integrating groups of data from source code with the expertise of a software system’s evaluators. A process for the extraction of elements from source code and Analytical Hierarchical Processing for assigning weights to these data are provided; k-Attractors clustering algorithm is then applied on these data, in order to produce system overviews and deductions. The methodology is evaluated on Apache Geronimo, a large Open Source Application Server, results are discussed and conclusions are presented together with directions for future work.

Βασική επιδίωξη της παρούσας διατριβής είναι η διερεύνηση των δυνατοτήτων του πεδίου της επιστήμης των υπολογιστών που πραγματεύεται την αποθήκευση και την επεξεργασία πληροφορίας, μέσα στο περιβάλλον που έχουν σχηματίσει οι σύγχρονες εφαρμογές. Τα τελευταία χρόνια, η πληροφορία που είναι διαθέσιμη σε ηλεκτρονική μορφή, έχει γιγαντωθεί με αποτέλεσμα να είναι αναγκαία η ανάπτυξη νέων τεχνικών για την αποτελεσματική αποθήκευση και επεξεργασία αυτής. Δύο πολύ χαρακτηριστικές και σημαντικές εφαρμογές, στις οποίες ανακύπτουν συνεχώς νέα προβλήματα, είναι η διαχείριση Βιολογικών δεδομένων, όπως π.χ. οι ακολουθίες γονιδιωμάτων, καθώς και η διαχείριση πληροφορίας από τον παγκόσμιο ιστό, όπως π.χ. τα έγγραφα HTML, XML ή οι συντομεύσεις (urls). Στόχος είναι ανάπτυξη δομών δεικτοδότησης πάνω στην πληροφορία έτσι ώστε τα σχετικά ερωτήματα με αυτή να απαντώνται αποδοτικά και πολύ πιο γρήγορα από το να ψάχναμε εκτενώς μέσα σε αυτή. Χαρακτηριστικά τέτοια ερωτήματα είναι η εύρεση προτύπων (pattern matching) ή ο εντοπισμός επαναλαμβανόμενων μοτίβων (motif extraction). Πιο συγκεκριμένα, τα ϑέματα στα οποία εστίασε η παρούσα διατριβή είναι τα ακόλουϑα: - Εντοπισμός Περιοδικοτήτων σε συμβολοσειρές. Στην ενότητα αυτή δίνεται μια σειρά από αλγόριθμους για την εξαγωγή περιοδικοτήτων από συμβολοσειρές. Δίνονται αλγόριθμοι για την εξαγωγή μέγιστων επαναλήψεων, της περιόδου του καλύμματος και της ρίζας μιας συμβολοσειράς. Οι αλγόριθμοι αυτοί χρησιμοποιούν ώς βάση το δένδρο επιθεμάτων και οι περισσότεροι από αυτούς είναι γραμμικοί. - Δεικτοδότηση Βεβαρημένων Ακολουθιών. Στην επόμενη ενότητα η μελέτη εστιάζει στην δεικτοδότηση βεβαρημένων ακολουθιών, καθώς και στην απάντηση ερωτημάτων σε αυτές όπως η εύρεση προτύπων, η εύρεση επαναλήψεων, η εύρεση καλυμμάτων, κ.α.. Οι βεβαρημένες ακολουθίες είναι ακολουθίες όπου σε κάθε ϑέση τους έχουμε εμφάνιση όλων των συμβόλων του αλφαβήτου της ακολουθίας, έχοντας λάβει ένα συγκεκριμένο βάρος. Οι βεβαρημένες ακολουθίες αναπαριστούν βιολογικές ακολουθίες είτε νουκλεοτιδίων είτε αμινοξέων και στην ουσία περιγράφουν την πιθανότητα εμφάνισης ενός συμβόλου του αλφαβήτου σε μια συγκεκριμένη ϑέση της ακολουθίας ή κάποιες συγκεκριμένες βιολογικές ιδιότητες που διαθέτουν οι ρυθμιστικές πρωτεΐνες σε κάθε ϑέση της ακολουθίας. Για την διαχείριση αυτών των ιδιόμορφων ακολουθιών προτείνεται ως δομή δεικτοδότησης το βεβαρημένο δένδρο επιθεμάτων (Weighted Suffix Tree), ένα δένδρο με παρόμοια δομικά χαρακτηριστικά με αυτά του γενικευμένου δένδρου επιθεμάτων. Στην παρούσα εργασία δίνεται ο ορισμός του βεβαρημένου δένδρου επιθεμάτων και αλγόριθμοι κατασκευής του σε γραμμικό χρόνο και χώρο. -Εξαγωγή μοτίβων από βεβαρημένες Ακολουθίες. Με την χρήση του βεβαρημένου δένδρου επιθεμάτων υλοποιούνται ένα σύνολο αλγόριθμων εξαγωγής επαναληπτικών δομών από βεβαρημένες ακολουθίες. Πιο συγκεκριμένα, δίνονται αλγόριθμοι για την εύρεση μέγιστων ευγών,επαναλαμβανόμενων μοτίβων και κοινών μοτίβων από περισσότερες της μίας βεβαρημένες ακολουθίες. - Αλγόριθμοι Σύστασης Σελίδων Παγκόσμιου Ιστού με χρήση τεχνικών επεξεργασίας συμβολοσειρών. Αρκετές εφαρμογές παγκόσμιου ιστού (συστήματα σύστασης ή συστήματα κρυφής μνήμης) προσπαθούν να προβλέψουν τις προθέσεις ενός επισκέπτη είτε για να του προτείνουν είτε για να προφορτώσουν μία σελίδα. Για το σκοπό αυτό προσπαθούν να εκμεταλλευτούν οποιαδήποτε εμπειρία που έχει καταγραφεί στο σύστημα από προηγούμενες προσπελάσεις. Προτείνεται νέος τρόπος δεικτοδότησης και αναπαράστασης της πληροφορίας που εξάγεται από τα διαθέσιμα δεδομένα, όπως οι προσβάσεις των χρηστών από τα logfilesκαι το περιεχόμενο των σελίδων. Για την εξόρυξη γνώσης από τα παραπάνω δεδομένα, αυτά αναπαριστώνται ως συμβολοσειρές και στη συνέχεια επεξεργάζονται και δεικτοδοτούνται από ένα γενικευμένο βεβαρημένο δένδρο επιθεμάτων. Το δένδρο αυτό συμπυκνώνει αποδοτικά τα πιο συχνά αλλά και πιο ουσιαστικά μοτίβα προσπελάσεων και χρησιμοποιείται, αφότου κατασκευαστεί, σαν ένα μοντέλο για την πρόβλεψη των κινήσεων τον επισκεπτών ενός ιστοτόπου. / The basic goal of this thesis is to explore the possibilities of the field of computer science that deals with storing and processing information in the environment that formed by the modern applications. In recent years, the information that is available in electronic form, has met an enormous growth. Thus it is necessary to develop new techniques for efficient storage and processing. Two very specific and important applications in which constantly new problems arise are, the management of biological data, such as genome sequences, and the management information from the Web, such as documents HTML, XML or shortcuts (urls). The objective is the development of data structures for indexing information so that the questions are able to be answered in less time than looking explicitly in information. Such questions are to find patterns (pattern matching) or the identification of repeated motifs (motif extraction). In particular, the issues on which this thesis has focused are: - Locating Periodicities in strings. This section provides a series of algorithms for the extraction of periodicities of strings. We propose algorithms for the extraction of maximum repetitions of the cover, period and the seed of a string. The algorithms used are based on suffix tree and they are optimal. - Weighted Sequences indexing. In the next section, the study focuses on indexing of weighted sequences, and to answer questions like finding models, pairs, covers etc. in them. The weighted sequences are sequences where each position consists of all the symbols of the alphabet in sequence, having each one a specific weight. For the management of these sequences a particular indexing structure is proposed with the name Weighted Suffix Tree, a tree with structural features similar to those of the generalized suffix tree. In this work we propose the definition of the weighted suffix tree and construction algorithms in linear time and memory space. With the utilization of weighted suffix tree on a set of weighted sequences we propose algorithms for extracting repetitive structures from a set of weighted sequences. More specifically, we propose algorithms for finding maximum pairs, repeated motifs and common patterns of more than one weighted sequences -Recommendation Algorithms for web pages using strings processing algorithms. Several web applications (Recommendation systems or cache systems) want to predict the intentions of a visitor in order to propose or to preload a webpage. For this purpose systems try to exploit any experience that is recorded in the system from previous accesses. A new method for indexing and representing of information extracted is proposed upon the recorder data, from the user accesses in log files and content pages. For extracting knowledge from these data, the information is represented as strings and then treated and processed as weighted sequences. All these sequences are indexed by a generalized weighted sequence tree.

Οι Δομές Δεδομένων είναι ένας από τους σημαντικότερους και ιστορικότερους κλάδους της Επιστήμης των Υπολογιστών, με συνεχή εξέλιξη από τη δεκαετία του εβδομήντα μέχρι σήμερα, παρέχοντας λύσεις σε θεμελιώδη προβλήματα σε ταξινόμηση, οργάνωση, διαχείριση και αναζήτηση πληροφορίας. Παράλληλα, η ανάπτυξη σύγχρονων κλάδων της Επιστήμης των Υπολογιστών όπως τα Σύγχρονα, Δικτυοκεντρικά Πληροφοριακά Συστήματα και η Βιοπληροφορική, έφερε μαζί της την έκρηξη των δεδομένων. Η ανάγκη αποδοτικής διαχείρισης της παρεχόμενης πληροφορίας καθίσταται έτσι πιο επιτακτική από ποτέ. Στα πλαίσια αυτής της διατριβής αναγνωρίζοντας την ανάγκη για αποδοτική διαχείριση πληροφορίας σε όλα τα επίπεδα, παρουσιάζουμε τη μελέτη και την πρόταση λύσεων σε σύγχρονα προβλήματα στους χώρους: της Διαχείρισης Συμβολοσειρών, της Αναδιοργάνωσης Δικτυακών Τόπων, της Ανακάλυψης Web Services με υποστήριξη χαρακτηριστικών Ποιότητας Υπηρεσίας και της Προσωποποιημένης Ανάκτησης Πληροφορίας στο Διαδίκτυο. Σε αυτή την κατεύθυνση, στον τομέα της Διαχείρισης Συμβολοσειρών, παραθέτουμε αλγορίθμους σε θεμελιώδη προβλήματα στο χώρο της διαχείρισης Σταθμισμένων Ακολουθιών (weighted sequences), όπως ταίριασμα προτύπου, εύρεση επαναληπτικών δομών, και συνεχίζουμε δίνοντας απλοποιητικές αλλά βέλτιστες λύσεις σε προβλήματα περιοδικοτήτων σε συνήθεις συμβολοσειρές, όπως τα προβλήματα εύρεσης όλων των καλυμμάτων μιας συμβολοσειράς, εύρεσης της περιόδου μιας συμβολοσειράς και εύρεσης όλων των φύτρων μιας συμβολοσειράς. Στην Αναδιοργάνωση Δικτυακών Τόπων, παραθέτουμε δυο διαφορετικές μετρικές για την αποτίμηση της αντικειμενικής αξίας των ιστοσελίδων του κάθε ιστοτόπου. Αυτές οι μετρικές παραλλάζουν τις προσβάσεις που δέχεται κάποια ιστοσελίδα με τρόπο που καταδεικνύει την αντικειμενική αξία της ιστοσελίδας. Από πειραματική αποτίμηση των μετρικών, προκύπτει ότι παρέχουν ακριβή πληροφόρηση για τα σημεία του δικτυακού τόπου που χρήζουν αναδιοργάνωσης. Στη συνέχεια δίνουμε μια μέθοδο για τον εντοπισμό σημαντικών τμημάτων μεγαλύτερου μεγέθους στο δικτυακό τόπο και παρουσιάζουμε μια σειρά μεθόδων τόσο σε τεχνικό όσο και θεωρητικό επίπεδο για την αναδιοργάνωση ενός δικτυακού τόπου. Στον τομέα της Ανακάλυψης Web Services, εξετάζουμε την Ανακάλυψη που πληροί περιορισμούς ως προς την παρεχόμενη Ποιότητα Υπηρεσίας. Αρχικά, παρουσιάζονται δυο απλές μέθοδοι για την καταχώριση χαρακτηριστικών ποιότητας υπηρεσίας επεκτείνοντας υπάρχοντα πρότυπα υλοποίησης Web Service. Στη συνέχεια παρουσιάζουμε έναν αλγόριθμο για την ανακάλυψη του σεναρίου εκτέλεσης μιας ακολουθίας (workflow) από συνεχόμενες Web Services, που ελαχιστοποιεί το συνολικό χρόνο εκτέλεσης. Μια σειρά από ευριστικές μεθόδους παρουσιάζονται επίσης, για την υλοποίηση σε πρακτικό επίπεδο του προτεινόμενου αλγορίθμου, οι οποίες αποτιμούνται πειραματικά. Τέλος, στον τομέα της Προσωποποιημένης Ανάκτησης Πληροφορίας στο Διαδίκτυο εξετάζουμε διαφορετικές τεχνικές προσωποποίησης των αποτελεσμάτων των μηχανών αναζήτησης. Η πρώτη τεχνική εφαρμόζει μετα-κατηγοριοποίηση των αποτελεσμάτων και παρουσίασή τους ανάλογα με τη σειρά ενδιαφέροντος του χρήστη ως προς τις κατηγορίες των αποτελεσμάτων. Η δεύτερη τεχνική, βασίζει την προσωποποίηση στην έμμεση απεικόνιση των ενδιαφερόντων χρήστη στις κατηγορίες του Open Directory Project, επεκτείνει μια τεχνική που έχει πρόσφατα προταθεί, τους ιδεατούς κόμβους συσχέτισης κατηγοριών, και χτίζει πολλαπλά επίπεδα ιδεατών κόμβων για την επίτευξη πιο εκλεπτυσμένης προσωποποίησης. Κλείνοντας, παρουσιάζουμε την επέκταση της λογικής της μεθόδου προσωποποίησης για την κατασκευή εστιασμένων συλλεκτών. / Data Structures is one of the most important and most historical sectors of Computer Science, being under continuous development since the seventies. Data Structuring has offered solutions to fundamental problems in sorting, organising, and retrieving information. Meanwhile, the development of the modern fields of Computer Science such as Modern, Net-centric Information Systems and Bioinformatics has signalled a data blow-up. Therefore, the need for efficient information management has become a necessity. In this Thesis, having recognized the need for efficient information management at every level, we present a study and solutions to contemporary problems in the areas of: String Processing, Website Reorganization, Web Service retrieval with support for Quality of Service characteristics, and Personalized Information Retrieval on the Web. In the area of String Processing, we present algorithms for solving fundamental problems in Weighted Sequence Processing, such as Pattern Matching, Repetitive Structures Detection and we continue by giving simplifying yet optimal solutions to periodicity problems in ordinary sequences, namely detecting all covers in a sequence, detecting the period of a sequence and detecting all the seeds of a sequence. In the area of Website Reorganization, we present two different metrics for evaluation of the objective importance of each website's pages. These metrics modify the accesses each page receives in order to present the actual page importance. We have seen from the experimental evaluation of those metrics that they provide accurate information about the areas inside the website in need of reorganization. Furthermore, we present a method to detect larger important parts inside the website and we present methods for website reorganisation both from a technical and from a theoretical viewpoint. In the area of Web Service Retrieval we are coping with retrieval under constraints for the provided Quality of Service (QoS). Firstly, we present two simple methods to register QoS information by extending existing Web Service protocols. Secondly, we present an algorithm to discover the execution scenario for a sequence of contiguous Web Services that minimizes the total execution time. A series of heuristics to implement the above algorithm is also presented. We also present an extensive experimental evaluation of those heuristics. Ultimately, we present different personalization techniques for personalized Web Information Retrieval. The first technique, applies post-categorization of search engine results and presents them according to user preferences with respect to the results' categories. The second technique is based on implicit mapping of user preferences to the categories of the Open Directory Project, it extends a recently proposed technique, namely virtual nodes for associating categories, and builds multiple layers of nodes to achieve more elaborate personalization. Finally, we present the extension of personalization methods in order to build focused crawlers.

Στα πλαίσια της διδακτορικής μας διατριβής ασχοληθήκαμε με προβλήματα διαχείρισης δικτυακών πληροφοριακών συστημάτων που βασίζονται σε τεχνολογίες παγκόσμιου ιστού (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 κύριος στόχος της παρουσίασης των λύσεων αυτών είναι να επιδειχθεί ότι οι προτεινόμενοι αποδοτικοί αλγόριθμοι, που παρουσιάστηκαν στα προηγούμενα κεφάλαια, έχουν εφαρμογή σε πολλαπλά προβλήματα διαφορετικών επιστημονικών και τεχνολογικών πεδίων που χρησιμοποιούν δικτυακά πληροφοριακά συστήματα και εφαρμογές παγκόσμιου ιστού. / In our PhD dissertation we dealt with performance issues in network - centric information systems, netcentric information systems and web information systems. Netcentric approach attempts to depict the augmenting tendency to use the network communication in information systems and web applications in order to provide, to publish, to distribute and to communicate online services and information. The key aim of our doctoral thesis is a) the quality at the service provision, v) the reduction of discovery time and c) the personalization of services and information in network information systems and applications that are based on web engineering technologies. Initially, we studied, designed and implemented efficient algorithms concerning Web Services technologies that have been designed to facilitate interoperable service integration using network infrastructure. Web Services Architecture has been standardized by W3 Consortium (http://www.w3.org) as the technological framework and it has received the wide support of the information technology scientific community as well as the information technology (IT) professionals and industry worldwide. In the first section we introduce a new categorization and comparative presentation of the available algorithmic solutions for service management and discovery. Then, we introduce a series of new efficient algorithms that ensure quality of service provision and improve time complexity in service discovery. Overall in the first part of the thesis we present: - Efficient algorithms for dynamic Web Service selection taking into account non-functional specifications (Quality of Web Service – QoWS) and performance issues during Web Service (WS) consumption attempt (i.e. QoWS enabled WS discovery). - Efficient algorithms for service management and discovery in network centric information systems that are based on decentralized network approaches specifically designed for WS discovery. In the sequel, we propose efficient adaptive methods for personalized web searching. In this way we provide performance improvement both for the internal management and discovery functionality of web based net-centric information systems as well as for the systems’ output that is the end-user information. In particular, in the second section, we introduce a series of three new algorithms for personalized searching. The proposed algorithms are mainly based on link metrics techniques. Their main advantage is that they allow, with the use of a simple methodology, search results personalization, with minimum overhead in terms of storage volume and computation time. We achieve personalized search using link analysis in a personalized graph much smaller one than the whole web graph. The personalized graph is shaped taking advantage of semantic taxonomies. Summarizing the novel research results of this second section are the following: - Efficient algorithms for personalized web information searching. - Adaptive presentation mechanisms of search results with the use of multiple levels of novel categorization. - Extension that allows the adoption of the algorithms for the case of focused web crawling mechanisms, which constitute an alternative personalized searching approach. Finally in the third and last section of our thesis, we present a series of applications, architectures and frameworks of different web based net-centric information environments cases, in which we apply our techniques for service management and personalized information discovery. The main objective of this presentation is to show that the efficient algorithms presented in the previous sections, have multiple potentials of application in problems of different research and technological areas using web based net-centric informative systems and web applications. Cases presented include network management information systems, e-learning approaches, semantic mining and multimedia retrieval systems, web content and structure maintenance solutions and agricultural information systems.

Η διπλωματική εργασία διαπραγματεύεται την εφαρμοσιμότητα του peer-to-peer υπολογισμού και τεχνικών στα ασύρματα κινητά ad-hoc δίκτυα και στα δίκτυα αισθητήρων. Παρουσιάζεται μια παραλλαγή ενός νέου P2P πρωτοκόλλου (Energy Level Distributed Tree) που σαν κύρια λειτουργία του έχει την αύξηση του προσδόκιμου λειτουργίας ενός δικτύου αισθητήρων. Επίσης, γίνεται αναφορά στα πιο δημοφιλή εργαλεία προσομοίωσης για P2P πρωτόκολλα δρομολόγησης και παρουσιάζεται ένα νέο εργαλείο, d-p2p-sim, με δυνατότητα προσομοίωσης εκατομμυρίων κόμβων. Τέλος, εξετάζουμε την απόδοση ενός νέου P2P πρωτοκόλλου δρομολόγησης, του Nested Balanced Distributed Tree, που απαντά με βέλτιστο τρόπο ερωτήμα ακριβούς ταιριάσματος και ερωτήματα διαστήματος παρουσιάζοντας παράλληλα δύο νέους αλγορίθμους αναζήτησης για αυτό. / In this master thesis we study the applicability of the peer-to-peer computing and techniques on wireless ad-hoc networks and sensor-nets. We propose a simplified mapping of an optimal P2P protocol (NBDT) onto sensor-nets, the so called Energy Level Distributed Tree (ELDT), which has one main operation: the life expectancy of a sensor-net. Furthermore, are examined the most popular Peer-to-Peer simulators and is presented a new distributed simulator for P2P routing algorithms. The key feature of the proposed simulator is the ability to simulate millions of peers. Finally, is presented a revised version of the NBDT protocol which is hot-spot free and achieves a better load distribution introducing a negligible routing overhead.

H διατριβή διερευνά προβλήματα αποδοτικής οργάνωσης χωροταξικών δεδομένων, προτείνει συγκεκριμένες δενδρικές δομές για τη διαχείρισή τους και, τέλος, δίνει παραδείγματα χρήσης τους σε ειδικές περιοχές εφαρμογών. Το πρώτο κεφάλαιο ασχολείται με το γεωμετρικό πρόβλημα της εύρεσης των ισo-προσανατολισμένων ορθογωνίων που περικλείουν ένα query αντικείμενο που μπορεί να είναι ένα ισο-προσανατολισμένο ορθογώνιο είτε σημείο ή κάθετο / οριζόντιο ευθύγραμμο τμήμα. Για την επίλυσή του προτείνεται μια πολυεπίπεδη δενδρική δομή που βελτιώνει τις πολυπλοκότητες των προηγούμενων καλύτερων λύσεων. Το δεύτερο κεφάλαιο εξετάζει το πρόβλημα της ανάκτησης σημείων σε πολύγωνα. H προτεινόμενη γεωμετρική δομή είναι επίσης πολυεπίπεδη και αποδοτική όταν το query πολύγωνο έχει συγκεκριμένες ιδιότητες. Το τρίτο κεφάλαιο ασχολείται με την εφαρμογή δενδρικών δομών σε δύο βιομηχανικά προβλήματα. Το πρώτο αφορά στη μείωση της πολυπλοκότητας ανίχνευσης συγκρούσεων κατά την κίνηση ενός ρομποτικού βραχίονα σε μια επίπεδη σκηνή με εμπόδια. Ο αλγόριθμος επίλυσης κάνει χρήση μιας ουράς προτεραιότητας και μιας UNION-FIND δομής ενώ αξιοποιεί γνωστές δομές και αλγόριθμους της Υπολογιστικής Γεωμετρίας όπως υπολογισμός κυρτών καλυμμάτων, έλεγχος polygon inclusion, κλπ. Το δεύτερο πρόβλημα ασχολείται με το σχεδιασμό απαιτήσεων υλικών (MRP) σε ένα βιομηχανικό σύστημα παραγωγής. Για το σκοπό αυτό αναπτύχθηκε ένας MRP επεξεργαστής που χρησιμοποιεί διασυνδεμένες λίστες και εκτελείται στην κύρια μνήμη για να είναι αποδοτικός. Το τελευταίο κεφάλαιο εξετάζει το πρόβλημα του ελέγχου της παραγωγής και συγκεκριμένα της δρομολόγησης εργασιών. Στο πλαίσιο αυτό σχεδιάστηκε και υλοποιήθηκε ένα ευφυές σύστημα δρομολόγησης σε περιβάλλον ροής που συνδυάζει γνωσιακή τεχνολογία και προσομοίωση με on-line έλεγχο προκειμένου να υποστηρίξει το διευθυντή παραγωγής στη λήψη αποφάσεων. / Τhe dissertation examines problems of efficient organization of spatial data, proposes specific tree structures for their management, and finally, gives examples of their use in specific application areas. The first chapter is about the problem of finding the iso-oriented rectangles that enclose a query object which can be an iso-oriented rectangle either a point or a vertical / horizontal line segment. A multilevel tree structure is proposed to solve the problem which improves the complexities of the best previous known solutions. The second chapter examines the problem of point retrieval on polygons. The proposed geometric structure is also multileveled and efficient when the query polygon has specific properties. The third chapter is about the application of tree structures in two manufacturing problems. The first one concerns the reduction in the complexity of collision detection as a robotic arm moves on a planar scene with obstacles. For the solution a priority queue and a UNION-FIND structure are used, whereas known data structures and algorithms of Computational Geometry such as construction of convex hulls, polygon inclusion testing, etc. are applied. The second problem is about material requirements planning (MRP) in a manufacturing production system. To this end an MRP processor was developed, which uses linked lists and runs in main memory to retain efficiency. The last chapter examines the production control problem, and more specifically the job scheduling problem. In this context, an intelligent scheduling system was designed and developed for flow shop production control which combines knowledge-based technology and simulation with on-line control in order to support the production manager in decision making.