Η παρούσα διπλωματική εργασία πραγματεύεται την μελέτη, τον σχεδιασμό και την κατασκευή ενός ηλεκτρονικά ελεγχόμενου μηχανικού φορτίου. Η εργασία αυτή εκπονήθηκε στο Εργαστήριο Ηλεκτρομηχανικής Μετατροπής Ενέργειας του Τμήματος Ηλεκτρολόγων Μηχανικών και Τεχνολογίας Υπολογιστών της Πολυτεχνικής Σχολής του Πανεπιστημίου Πατρών. Σκοπός είναι η δημιουργία ενός μηχανικού φορτίου του οποίου το προφίλ μπορεί να ελέγχεται με την χρήση ψηφιακού μικροελεγκτή. Αρχικά, εξετάζεται η θέση που κατέχει το μηχανικό φορτίο σε ένα ηλεκτρικό κινητήριο σύστημα και παρουσιάζονται οι χαρακτηριστικές καμπύλες των διάφορων τύπων μηχανικών φορτίων. Στη συνέχεια, μελετώνται η βασική αρχή λειτουργίας, οι μαθηματικές εξισώσεις καθώς και τα κατασκευαστικά χαρακτηριστικά των μηχανών συνεχούς ρεύματος αλλά και της μηχανής που χρησιμοποιήθηκε στην κατασκευή. Στο επόμενο βήμα, γίνεται μια θεωρητική ανάλυση του κυκλώματος της πλήρους γέφυρας που κατασκευάστηκε καθώς και όλων των υπόλοιπων κυκλωμάτων και στοιχείων που είναι αναγκαία για την λειτουργία της. Επιπροσθέτως, αναλύεται η μέθοδος παλμοδότησης των διακοπτικών στοιχείων του μετατροπέα, που είναι η Διαμόρφωση Εύρους Παλμών (PWM) καθώς και τα ιδιαίτερα χαρακτηριστικά του μικροελεγτή που χρησιμοποιήθηκε. Για το συνολικό σύστημα, αποτελούμενο από την μηχανή συνεχούς ρεύματος και τον μετατροπέα τύπου πλήρους γέφυρας, δημιουργήθηκε ένα μαθηματικό μοντέλο στο περιβάλλον Simulink για να ελεγχθεί η συμπεριφορά του. Τέλος, αναλύονται τα τεχνικά χαρακτηριστικά όλων των κυκλωμάτων που κατασκευάστηκαν και παρατίθενται τα παλμογραφήματα που προέκυψαν από τα πειράματα που διενεργήθηκαν μετά την ολοκλήρωση της κατασκευής. / This thesis deals with the study, design and construction of an electronically controlled mechanical load. The work was conducted in the Laboratory of Electromechanical Energy Conversion, Department of Electrical and Computer Engineering School of Engineering, University of Patras. The aim is to create a mechanical load whose profile can be controlled using digital microcontroller. First, was considered the position of the mechanical load in an electric driving system and shows the characteristic curves of various types of mechanical loads. Then was studied the basic principle of operation, mathematical equations and the construction of DC machines and the machine used in construction. The next step is a theoretical analysis of the full bridge circuit that is constructed and all other circuits and components necessary for its operation. In addition, explains the method of interrupted pulses data converter, which is shaping pulse width (PWM) and the characteristics of icroconroler which is used. For the total system, consisting of the DC machine and type full bridge converter, a mathematical model in Simulink environment to verify its behavior. Finally, analyzing the technical characteristics of all circuits built out and the curves obtained from experiments carried out after the completion of construction.

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη της θεωρίας της Near Complete Decomposability (NCD) και η εφαρμογή της στην ανάλυση της απόδοσης ενός υπολογιστικού συστήματος, του οποίου η μοντελοποίηση με παραδοσιακές τεχνικές οδηγεί σε απαγορευτικά μεγάλο χώρο κατάστασης. Αρχικά, παραθέτουμε τα βασικά σημεία της θεωρίας όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία (Courtois, 1977), ενώ στη συνέχεια προβαίνουμε στη μοντελοποίηση ενός υποθετικού σταθμού εργασίας κάποιου πολυεπεξεργαστικού συστήματος, στο οποίο εκτελούνται ανά πάσα στιγμή το πολύ Κ έργα. Ο σταθμός εργασίας που μελετάμε διαθέτει buffer πεπερασμένου μεγέθους και είναι επιφορτισμένος με τη συγκέντρωση και το συνδυασμό των επιμέρους υποέργων κάθε έργου και την αποθήκευση του στη μνήμη. Οι κλασικές τεχνικές μοντελοποίησης του buffer οδηγούν σε ένα μοντέλο με πολύ μεγάλο χώρο κατάστασης. Ωστόσο εμείς μοντελοποιούμε μία συναθροιστική εκδοχή του αρχικού μοντέλου, η οποία υπό αρκετά ρεαλιστικές συνθήκες χαίρει της NCD ιδιότητας. Την ιδιότητα αυτή του μοντέλου μας τη δικαιολογούμε τόσο διαισθητικά, όσο και μαθηματικά. Επίσης, επιβεβαιώνουμε πως το NCD μοντέλο πετυχαίνει υψηλής ποιότητας εκτίμηση των πιθανοτήτων μόνιμης κατάστασης και μίας σειράς άλλων χρήσιμων μετρικών, με σημαντικά μικρότερο υπολογιστικό κόστος σε σχέση με το αρχικό μοντέλο, εκτελώντας μία σειρά μετρήσεων στο περιβάλλον Matlab. Παράλληλα, η αξιοποίηση του NCD μοντέλου αυξάνει σημαντικά την ικανότητά μας να ερμηνεύσουμε τη δυναμική συμπεριφορά του συστήματος καθώς αυτό οδεύει προς μια κατάσταση στατιστικής ισορροπίας. Τέλος, επιχειρούμε μία σειρά από “educated guesses” για πιθανές κλάσεις συστημάτων τα οποία θα μπορούσαν να αναλυθούν με μεθοδολογία αντίστοιχη με αυτήν που ακολουθήσαμε εμείς στο παρόν κείμενο. / The purpose of this diploma dissertation is, on one hand the brief study of the theory of Near Complete Decomposability (NCD), and on the other hand the application of NCD in the analysis of a system, the modeling of which leads to a prohibitively large state space. First, we point out the fundamental mathematical principles of NCD as established by Courtois in his classic monograph (Courtois, 1977). Then, we proceed to the modeling of a hypothetical service station (R) of a multiprocessing computer system, which executes at most K jobs simultaneously. R has a finite buffer and its duty is to combine the arriving tasks into a single job and store it to memory. The usual modeling techniques applied to this “task buffer”, lead to a model with extremely large state space. So, we construct a lumped model instead, which enjoys the property of NCD. We prove this, using intuitive arguments as well as mathematical ones. Then, we confirm that the NCD model achieves a reliable estimation of the steady state probability vector and other important metrics, with significantly reduced computational complexity in comparison with the initial model. Furthermore, the exploitation of the NCD model increases significantly our ability to understand the dynamics of our system and to interpret aspects of its transient behavior towards statistical equilibrium. Finally, we make a number of “educated guesses” about possible classes of systems that could be analyzed using the same kind of techniques we used in this dissertation.

Σκοπός της παρούσας διπλωματικής διατριβής είναι η μελέτη και ανάπτυξη ενός νέου αλγοριθμικού πλαισίου Συνεργατικής Διήθησης(CF) για την παραγωγή συστάσεων. Η μέθοδος που προτείνουμε, βασίζεται στην εκμετάλλευση της ιεραρχικής διάρθρωσης του χώρου αντικειμένων και πατά διαισθητικά στην ιδιότητα της ``Σχεδόν Πλήρης Αναλυσιμότητας'' (NCD) η οποία είναι συνυφασμένη με τη δομή της πλειοψηφίας των ιεραρχικών συστημάτων. Η Συνεργατική Διήθηση αποτελεί ίσως την πιο πετυχημένη οικογένεια τεχνικών για την παραγωγή συστάσεων. Η μεγάλη απήχησή της στο διαδίκτυο αλλά και η ευρεία εφαρμογή της σε σημαντικά εμπορικά περιβάλλοντα, έχουν οδηγήσει στη σημαντική ανάπτυξη της θεωρίας την τελευταία δεκαετία, όπου μια ευρεία ποικιλία αλγορίθμων και μεθόδων έχουν προταθεί. Ωστόσο, παρά την πρωτοφανή τους επιτυχία οι CF μέθοδοι παρουσιάζουν κάποιους σημαντικούς περιορισμούς συμπεριλαμβανομένης της επεκτασιμότητας και της αραιότητας των δεδομένων. Τα προβλήματα αυτά επιδρούν αρνητικά στην ποιότητα των παραγόμενων συστάσεων και διακυβεύουν την εφαρμοσιμότητα πολλών CF αλγορίθμων σε ρεαλιστικά σενάρια. Χτίζοντας πάνω στη διαίσθηση πίσω από τον αλγόριθμο NCDawareRank - μίας γενικής μεθόδου υπολογισμού διανυσμάτων κατάταξης ιεραρχικά δομημένων γράφων - και της σχετικής με αυτόν έννοιας της NCD εγγύτητας, προβαίνουμε σε μία μοντελοποίηση του συστήματος με τρόπο που φωτίζει τα ενδημικά του χαρακτηριστικά και προτείνουμε έναν νέο αλγοριθμικό πλαίσιο συστάσεων, τον Αλγόριθμο 1. Στο επίκεντρο της προσέγγισής μας είναι η προσπάθεια να συνδυάσουμε τις άμεσες με τις NCD, ``γειτονιές'' των αντικειμένων ώστε να πετύχουμε μεγαλύτερης ακρίβειας χαρακτηρισμό των πραγματικών συσχετισμών μεταξύ των στοιχείων του χώρου αντικειμένων, με σκοπό την βελτίωση της ποιότητας των συστάσεων αλλά και την αντιμετώπιση της εγγενούς αραιότητας και των προβλημάτων που αυτή συνεπάγεται. Για να αξιολογήσουμε την απόδοση της μεθόδου μας υλοποιούμε και εφαρμόζουμε τον Αλγόριθμο 1 στο κλασικό movie recommendation πρόβλημα και παραθέτουμε μια σειρά από πειράματα χρησιμοποιώντας τo MovieLens Dataset. Τα πειράματά μας δείχνουν πως ο Αλγόριθμος 1 με την εκμετάλλευση της ιδέας της NCD εγγύτητας καταφέρνει να πετύχει λίστες συστάσεων υψηλότερης ποιότητας σε σύγκριση με τις άλλες state-of-the-art μεθόδους που έχουν προταθεί στη βιβλιογραφία, σε ευρέως χρησιμοποιούμενες μετρικές (micro- και macro-DOA), αποδεικνύοντας την ίδια στιγμή πως είναι λιγότερο επιρρεπής στα προβλήματα που σχετίζονται με την αραιότητα και έχοντας παράλληλα ανταγωνιστικό προφίλ πολυπλοκότητας και απαιτήσεις αποθήκευσης. / The purpose of this master's thesis is to study and develop a new algorithmic framework for collaborative filtering (CF) to generate recommendations. The method we propose is based on the exploitation of the hierarchical structure of the item space and intuitively ``stands'' on the property of Near Complete Decomposability (NCD) which is inherent in the structure of the majority of hierarchical systems. Collaborative Filtering is one of the most successful families of recommendations methods. The great impact of CF on Web applications, and its wide deployment in important commercial environments, have led to the significant development of the theory, with a wide variety of algorithms and methods being proposed. However, despite their unprecedented success, CF methods present some important limitations including scalability and data sparsity. These problems have a negative impact of the quality of the recommendations and jeopardize the applicability of many CF algorithms in realistic scenarios. Building on the intuition behind the NCDawareRank algorithm and its related concept of NCD proximity, we model our system in a way that illuminates its endemic characteristics and we propose a new algorithmic framework for recommendations, called Algorithm 1. We focus on combining the direct with the NCD `` neighborhoods'' of items to achieve better characterization of the inter-item relations, in order to improve the quality of recommendations and alleviate sparsity related problems. To evaluate the merits of our method, we implement and apply Algorithm 1 in the classic movie recommendation problem, running a number of experiments on the standard MovieLens dataset. Our experiments show that Algorithm 1 manages to create recommendation lists with higher quality compared with other state-of-the-art methods proposed in the literature, in widely used metrics (micro- and macro- DOA), demonstrating at the same time that it is less prone to low density related problems being at the same time very efficient in both complexity and storage requirements.

Ο σκοπός αυτής της διατριβής είναι η ανεύρεση μεθόδων αποδοτικής οργάνωσης και διαχείρισης πολυδιάστατων αντικειμένων (multi-dimensional objects) προκειμένου να ανακαλυφθεί χρήσιμη γνώση. Αρχική αφορμή για αυτή τη μελέτη αποτέλεσαν οι ανάγκες μιας απαιτητικής εφαρμογής με σκοπό τη χαρτογράφηση του ανθρώπινου εγκεφάλου προκειμένου να εντοπιστούν επιληπτικές εστίες. Οι απαιτήσεις Αναπαράστασης και Διαχείρισης των Δεδομένων του Εγκεφάλου, έφεραν στην επιφάνεια δύο κεντρικά ερευνητικά προβλήματα: - Τις ιδιαιτερότητες των πολύπλοκων, μη-ομοιογενών, δικτυακών μερικές φορές, τρισδιάστατων αντικειμένων (τμημάτων του εγκεφάλου – brain objects). - Την ανάγκη για αποτελεσματική διαχείριση-χρήση γνωστών αλλά και παραγόμενων εξαρτήσεων δεδομένων και γνώσης (data and knowledge dependencies), η οποία μπορεί να αναβαθμίσει την απόδοση και τη δυναμική της εφαρμογής. Το μεγαλύτερο μέρος της μελέτης που αφορούσε αυτό το πρόβλημα, οδήγησε σε : - Διερεύνηση θεμάτων ανεύρεσης ομοιοτήτων (similarity search). Καθώς η συγκεκριμένη περιοχή διαθέτει μεγάλο εύρος εφαρμογών αλλά και ανοικτών προβλημάτων, αποτέλεσε τελικά μεγάλο μέρος της παρούσας διατριβής. Δεδομένου ότι πολλά από τα γεωμετρικά χαρακτηριστικά των δεδομένων αλλά και από τις εξαρτήσεις γνώσης που αφορούν τον ανθρώπινο εγκέφαλο, συναντώνται – καθ’ολοκληρία ή τμηματικά – σε πλήθος σύγχρονων πολυμεσικών (multimedia) εφαρμογών, τα παραπάνω προβλήματα εντάσσονται στα βασικά προβλήματα της έρευνας του τομέα των Βάσεων Δεδομένων. Επικεντρώνοντας την έρευνά στα παραπάνω προβλήματα, καταλήξαμε: • στον ορισμό νέων ευέλικτων τύπων δεδομένων, εννοιών και μοντέλων καθώς και εργαλείων και μεθόδων ταξινόμησης δεδομένων και γνώσης (βάση δεδομένων BDB και μοντέλα 3D-IFO και MITOS) οι οποίες οργανώνουν πιο ευέλικτα και αποδοτικά τα δεδομένα μας, με τρόπους που όχι μόνο κάνουν την πρόσβασή τους ευκολότερη αλλά αξιοποιούν παράλληλα τις ‘κρυμμένες’ μεταξύ τους σχέσεις για την άντληση επιπλέον γνώσης. • στον ορισμό νέων μεθόδων και δέντρων αναζήτησης, για : o τον αποδοτικό εντοπισμό τμηματικών ομοιοτήτων (partial similarity) ανάμεσα σε πολυδιάστατα αντικείμενα (Lui k-n-match και INTESIS) o την εξάλειψη της μεγάλης πτώσης της απόδοσης των δέντρων με την αύξηση των διαστάσεων των αντικειμένων (‘dimensionality curse’) (δομή Digenis). o την ανεύρεση χαρακτηριστικών/διαστάσεων με παρόμοια εξέλιξη στην πορεία του χρόνου – για πολυδιάστατα κυρίως αντικείμενα – με σκοπό τη μελέτη πιθανής αλληλεπίδρασής τους. Γενικά, η παρούσα μελέτη αποτελείται από δύο βασικά μέρη, τα οποία αναφέρονται σε δύο περιοχές με μεγάλη αλληλεπίδραση:  Τη Μοντελοποίηση σε Πολυμεσικές Βάσεις Δεδομένων  Την Αναζήτηση Ομοιοτήτων ανάμεσα σε Πολυδιάστατα Αντικείμενα Στο πρώτο κεφάλαιο αρχικά παρουσιάζεται το πρόβλημα της χαρτογράφησης του ανθρώπινου εγκεφάλου για τον εντοπισμό επιληπτικών εστιών, απ’όπου εγείρονται τα πρώτα προβλήματα αναπαράστασης και οργάνωσης τριδιάστατων αντικειμένων πολύπλοκης δομής και λειτουργικών σχέσεων και εξαρτήσεων μεταξύ τους. Σε μια πρώτη προσέγγιση προτείνεται το λογικό μοντέλο BDB (Brain Data Base) όπου εισάγονται νέοι τύποι οντοτήτων. Εδώ, ιδιαίτερο ενδιαφέρον παρουσιάζει η προσθήκη της ιεραρχικής διάταξης στο Σχεσιακό Μοντέλο, προκειμένου οι περιοχές του εγκεφάλου να οργανωθούν με βάση την πιθανότητα εμφάνισης επιληπτικής εστίας έτσι ώστε να βελτιώνονται στατιστικά οι χρόνοι ανάκτησής τους. Στη συνέχεια, η μελέτη επεκτείνεται σε άλλα – επόμενης γενιάς - είδη μοντέλων. Πιο συγκεκριμένα, οι ανάγκες της εφαρμογής μελετώνται με βάση ένα Σημαντικό (semantic model) - το μοντέλο IFO - και ένα Αντικειμενοστραφές Μοντέλο (object oriented model), με αποτέλεσμα τη δημιουργία των μοντέλων 3D-IFO και MITOS αντίστοιχα. Στο 3D-IFO εισήχθησαν νέοι τύποι δεδομένων προκειμένου να υποστηριχθούν αποδοτικά τα ιδιαίτερα δεδομένα μας καθώς και νέοι τελεστές για την καλύτερη διαχείριση των σύνθετων δεδομένων. Επιπλέον, εισήχθη ένας νέος constructor και ένα κατάλληλο πεδίο για την υποστήριξή του, προκειμένου να υποστηριχτεί η αναπαράσταση της διάταξης των μερών του εγκεφάλου με βάση κάποιο κριτήριο έτσι ώστε να διευκολυνθεί η μελλοντική απλή και συνδυαστική ανάκτηση πληροφορίας. Τέλος το αντικειμενοστραφές μοντέλο MITOS, εισάγει πάλι ένα νέο μοντέλο δεδομένων (MITOS Data Model - MDM) το οποίο συνεργάζεται με μία νέα γλώσσα ερωτημάτων (MITOS Query Language - MQL). Το μοντέλο MITOS εισάγει διάφορες καινοτομίες οι οποίες εξυπηρετούν μια περισσότερο εκφραστική και έξυπνη αναπαράσταση και διαχείριση πολυδιάστατων δεδομένων και γνώσης. Η μία από αυτές τις καινοτομίες είναι ο ορισμός ενός ακόμη βασικού χαρακτηριστικού των αντικειμένων (object characteristic), της σχέσης τους με το περιβάλλον, απεγκλωβίζοντάς την από την κατάσταση ή τη συμπεριφορά, όπου αποδυναμώνεται σαν έννοια. Η δεύτερη καινοτομία του MITOS η οποία αφορά την MQL σχετίζεται με την εισαγωγή ‘κλειδιού’ στους κανόνες (rules). Η διερεύνηση αυτής της δυνατότητας – η ιδέα προέρχεται από το χώρο των Βάσεων Δεδομένων – οδηγεί πράγματι σε ένα είδος κλειδιού, κατά την έννοια που θα μπορούσε να έχει στις Βάσεις Γνώσης και η οποία δεν μπορεί να είναι ακριβώς ίδια με την αντίστοιχη των Βάσεων Δεδομένων, λόγω των ειδοποιών διαφορών των δύο Βάσεων. Στο δεύτερο κεφάλαιο μελετάται η αναζήτηση ενός ελάχιστα διερευνημένου είδους ομοιότητας ανάμεσα σε πολυδιάστατα κυρίως αντικείμενα, της τμηματικής ομοιότητας (partial similarity). Η τμηματική ομοιότητα σε αντίθεση με τον ιδιαίτερα διερευνημένο τύπο της πλήρους ομοιότητας (full similarity), αναφέρεται σε πραγματικές ομοιότητες οι οποίες δεν είναι πλήρεις. Κι αυτό συμβαίνει γιατί ένα πολύ συνηθισμένο σενάριο κατά τη διερεύνηση ομοιοτήτων είναι το ακόλουθο: Συνήθως η ανεύρεση πλήρους ομοιότητας βασίζεται σε υπολογισμό αποστάσεων, όπως η Ευκλείδεια απόσταση, οι οποίες είναι συνάρτηση όλων των διαστάσεων των εμπλεκομένων αντικειμένων. Όταν λοιπόν υπάρχουν διαστάσεις με μεγάλες διαφορές, ακόμη κι αν είναι λίγες, αυξάνουν αρκετά την υπολογιζόμενη απόσταση έτσι ώστε οι αποστάσεις τέτοιων αντικειμένων που στην πραγματικότητα μπορεί να είναι όμοια, να καταλήγουν να έχουν μεγάλες τιμές και συνεπώς να μην ανιχνεύεται η ομοιότητά τους (π.χ. όμοια αντικείμενα με πολύ διαφορετικό χρώμα). Από την άλλη πλευρά, για αντικείμενα τα οποία διαφέρουν λίγο σε κάθε διάσταση (π.χ. λίγο διαφορετικό χρώμα, σχήμα, προσανατολισμό κ.λ.π.) και καταλήγουν να είναι στην πραγματικότητα συνολικά πολύ διαφορετικά, η υπολογιζόμενη μεταξύ τους απόσταση έχει μικρή τιμή, οπότε ανιχνεύονται σαν όμοια, χωρίς να είναι. Οι περισσότερες εργασίες οι οποίες έχουν μελετήσει την τμηματική ομοιότητα, έχουν εστιάσει σε γεωμετρικά δεδομένα. Η εργασία που επεκτείνεται σε πολυδιάστατα αντικείμενα γενικά, είναι η εργασία των Koudas et al., (VLDB 2006) και έχει οδηγήσει σε αξιόλογα αποτελέσματα στο θέμα της τμηματικής ομοιότητας. Εισάγει τις αποδοτικές μεθόδους k-n-match και frequent k-n-match, οι οποίες επιστρέφουν k αντικείμενα, όμοια με τα δοθέντα όχι σε όλες αλλά σε n διαστάσεις, αποφεύγοντας έτσι εκείνες τις λίγες διαστάσεις με τις μεγάλες διαφορές, οι οποίες οδηγούν σε παραπλανητικά αποτελέσματα. Παρόλ’αυτά αυτές οι μέθοδοι κρύβουν κάποιες αδυναμίες οι οποίες τελικά οδηγούν είτε σε ανεύρεση πλήρους ομοιότητας (όταν τελικά ληφθούν υπ’όψιν όλα τα n), είτε σε μία κατά περίπτωση μόνο (και σχεδόν τυχαία) ανίχνευση τμηματικής ομοιότητας (με τα κατάλληλα n’s τα οποία δεν πρέπει να είναι ούτε πολύ μεγάλα ούτε πολύ μικρά, αλλά δεν ορίζονται από κάποιο τύπο ή μέθοδο). Βασιζόμενοι σ’ αυτές τις μεθόδους, προτείνουμε δύο νέες τεχνικές οι οποίες όπως αποδεικνύεται μπορούν να εντοπίσουν πραγματικές τμηματικές ομοιότητες. Η πρώτη, η Lui k-n-match, επιτυγχάνει τον κατά προσέγγιση εντοπισμό των κατάλληλων n’s για τα k-n-matches, με τη βοήθεια της αλληλεπίδρασης με το χρήστη και του ελέγχου των αποδεκτών προτάσεων των k-n-matches. Πιο συγκεκριμένα, μέσω της μεθόδου k-n-match, προτείνεται για κάθε n ένα σύνολο αντικειμένων πιθανά όμοιων με το δεδομένο αντικείμενο του ερωτήματος (query object) . Ο χρήστης φιλτράρει αυτό το σύνολο, επιλέγοντας εκείνα τα αντικείμενα που θεωρεί πραγματικά όμοια με το δεδομένο. Αυτή η διαδικασία συνεχίζεται μέχρι αφού το n γίνει μεγαλύτερο από το ήμισυ των διαστάσεων των αντικειμένων, υπάρξει σύνολο προτεινόμενων αντικειμένων από το οποίο ο χρήστης δεν επιλέγει κανένα ως όμοιο . Μ’αυτόν τον τρόπο επιτυγχάνεται μεγαλύτερη εγκυρότητα των αποτελεσμάτων (λόγω της εμπλοκής του χρήστη) με περιορισμένο ταυτόχρονα αριθμό εκτελούμενων k-n-matches. Η δεύτερη μέθοδος (INTESIS) βασίζεται στην εξής παρατήρηση: στην ουσία όταν δύο αντικείμενα μοιάζουν αυτό συνήθως σημαίνει ότι μοιάζουν στα περισσότερα χαρακτηριστικά τους, καθένα από τα οποία αναπαριστάται και αντιπροσωπεύεται από ένα σύνολο (μικρό συνήθως) διαστάσεων-πεδίων του αντικειμένου. Εάν λοιπόν οριστεί από τους ειδικούς κάθε εφαρμογής αυτή η αντιστοιχία χαρακτηριστικών και διαστάσεων - δημιουργώντας υποσύνολα διαστάσεων - τότε μπορούν να συμβούν διαδοχικά τα παρακάτω: α) Να γίνει έλεγχος πλήρους ομοιότητας σε κάθε τέτοιο υποσύνολο διαστάσεων β) Να οργανωθούν αυτά τα υποσύνολα σε ισάριθμα ιεραρχικά δέντρα για την εύκολη και αποδοτική διαχείρισή τους. Η επιπλέον απλούστευση αυτής της επιλογής έγκειται στο ότι δεδομένου ότι τα εν λόγω υποσύνολα διαστάσεων θα είναι μικρά, είναι πολύ εύκολη η επιλογή δέντρου γι’ αυτά, αφού σχεδόν όλα τα ιεραρχικά δέντρα έχουν μεγάλη απόδοση όταν πρόκειται για μικρό αριθμό διαστάσεων. Συνεπώς ο αναλυτής της κάθε εφαρμογής μπορεί να χρησιμοποιήσει όποιο τέτοιο δέντρο κρίνει εκείνος σαν καλύτερο ( Το R*-tree είναι η δική μας πρόταση). Τελικά, για να ολοκληρωθεί η διαδικασία πρέπει να έχει οριστεί ένας ελάχιστος αριθμός απαιτούμενων όμοιων χαρακτηριστικών προκειμένου να θεωρηθούν δύο αντικείμενα όμοια. Για την αξιολόγηση αυτής της μεθόδου, πρέπει αρχικά να σημειωθεί ότι αναφέρεται σε συνολικό αριθμό διαστάσεων μικρότερο του 100 και συνεπώς σε σχετικά μικρό αριθμό δέντρων. Όπως είναι φανερό, σε μονο-επεξεργαστικό σύστημα οι τελικοί χρόνοι απόκρισης είναι το άθροισμα των χρόνων κάθε δέντρου. Λαμβάνοντας υπ’όψιν το ότι τα δέντρα λόγω του μικρού αριθμού διαστάσεων που αντιστοιχούν στο καθένα έχουν πολύ καλές αποδόσεις, βγαίνει εύκολα το συμπέρασμα ότι ο εκάστοτε τελικός χρόνος απόκρισης της μεθόδου - όντας ένα μικρό πολλαπλάσιο των πολύ μικρών χρόνων προσπέλασης των δέντρων - είναι αρκετά χαμηλός. Με δεδομένο ότι η χρήση κάθε δέντρου δεν προϋποθέτει την χρήση κάποιου άλλου πριν ή μετά, οι αναζητήσεις σε κάθε δέντρο μπορούν να γίνονται παράλληλα. Συνεπώς σε πολυεπεξεργαστικό σύστημα, ο συνολικός χρόνος απόδοσης μπορεί να μειωθεί σημαντικά, φτάνοντας μέχρι και το χρόνο που απαιτείται μόνο για αναζήτηση σε ένα δέντρο (όταν υπάρχουν τόσοι επεξεργαστές όσα και δέντρα). Φυσικά, εάν λάβει κανείς υπ’όψιν του ότι η τμηματική ομοιότητα αποτελεί ένα ιδιαίτερα απαιτητικό είδος τότε όχι μόνο οι χρόνοι απόκρισης σε πολυεπεξεργαστικό σύστημα αλλά και εκείνοι του συστήματος ενός επεξεργαστή, αποτελούν ικανοποιητικές αποδόσεις. Το τρίτο κεφάλαιο μελετά τη δυνατότητα δημιουργίας μιας νέας δομής η οποία δε θα ‘υποφέρει’ από τη μεγάλη πτώση της απόδοσης των δέντρων με την αύξηση των διαστάσεων των αντικειμένων (‘dimensionality curse’) ενώ ταυτόχρονα θα εξασφαλίζει καλή απόδοση και σε μικρό αριθμό διαστάσεων. Οι μέχρι τώρα μελέτες έχουν καταλήξει στο εξής συμπέρασμα: Τα γνωστά διαδεδομένα δέντρα αναζήτησης (είτε πρόκειται για δέντρα οργανωμένα βάση κατανομής χώρου (space partitioning) είτε για δέντρα βάση κατανομής δεδομένων (data partitioning)) αποδίδουν πολύ καλύτερα σε μικρό αριθμό διαστάσεων ενώ όσο αυτός ο αριθμός αυξάνει - ειδικά από 10 και πάνω – η απόδοση χειροτερεύει δραματικά. Το VA-File (σχήμα προσέγγισης διανύσματος) από την άλλη πλευρά - το οποίο είναι ένας απλός πίνακας-αρχείο γεωμετρικών προσεγγίσεων των αντικειμένων - με την αύξηση των διαστάσεων αποδίδει καλύτερα στην αναζήτηση ομοιοτήτων αλλά παρουσιάζει χαμηλή απόδοση σε μικρό αριθμό διαστάσεων. Προκειμένου να ξεπεραστεί αυτή η καθοριστική εξάρτηση της απόδοσης από το πλήθος των διαστάσεων των προς διαχείριση αντικειμένων, προτείνουμε τη νέα υβριδική δομή Digenis, η οποία παντρεύει τη λογική των δέντρων αναζήτησης με κείνη των VA αρχείων. Πιο συγκεκριμένα, ορίζεται και χρησιμοποιείται ένα στατικό παραμετροποιημένο δέντρο (δέντρο Digenis) σε εννοιολογικό επίπεδο ενώ σε φυσικό επίπεδο χρησιμοποιείται το αρχείο Digenis το οποίο κατασκευάζεται με βάση το δέντρο. Με αυτή τη συσχέτιση επιτυγχάνεται αναζήτηση σε μικρό μόνο μέρος του αρχείου κατά τη διαδικασία ανεύρεσης ομοιοτήτων ανάμεσα σε αντικείμενα πολλών αλλά και λίγων διαστάσεων, γεγονός που δίνει γενικότητα και ευελιξία στη μέθοδο. Πιο συγκεκριμένα, για το σχηματισμό του δέντρου, αρχικά ορίζονται οι οικογένειες αντικειμένων, οι οποίες αποτελούνται από αντικείμενα με μικρή απόσταση (βάση ενός προκαθορισμένου από τον εκάστοτε αναλυτή ορίου fl) και αντιπροσωπεύονται από το ‘μέσο’ αντικείμενο της οικογένειας (εάν δεν υπάρχει δημιουργείται για αυτό το ρόλο και μόνο). Κάθε κόμβος του δέντρου αντιπροσωπεύει-φιλοξενεί μία τέτοια οικογένεια. Το είδος των αποστάσεων που χρησιμοποιείται είναι η πλέον διαδεδομένη απόσταση, η Ευκλείδεια απόσταση, για την οποία ισχύει και η τριγωνική ανισότητα στην οποία θα βασιστεί μεγάλο μέρος της μεθόδου. Επίσης ένα δεύτερο όριο απόστασης (Lt) ορίζεται – από τον αναλυτή πάλι - σαν όριο με βάση το οποίο δύο αντικείμενα μπορούν να θεωρηθούν όμοια. Το δέντρο Digenis τελικά χτίζεται έχοντας ρίζα την πιο ‘κεντρική’ οικογένεια της περιοχής των αντικειμένων και κόμβους-παιδιά της τις ch πιο γειτονικές της οικογένειες, κάθε μία από αυτές έχει παιδιά της τις ch πιο γειτονικές της οικογένειες κ.ο.κ. Η δεδομένη ισχύ της τριγωνικής ανισότητας ανάμεσα στις Ευκλείδειες αποστάσεις των αντικειμένων-οικογενειών, αποδεικνύεται ένα χρήσιμο θεώρημα βάση του οποίου καθιστάται εφικτή η ασφαλής εξαίρεση μεγάλου μέρους του δέντρου από τους ελέγχους ομοιότητας, κατευθύνοντας τον τελικό έλεγχο σε μία μικρή περιοχή του. Αυτή η ανάλυση της αναζήτησης μέσα στο δέντρο είναι πολύ χρήσιμη σε ό,τι αφορά τη χρήση του αρχείου Digenis, όπου εκεί πραγματοποιείται η πραγματική αναζήτηση (φυσικό επίπεδο). Το αντίστοιχο αρχείο Digenis στο φυσικό επίπεδο σχηματίζεται εάν αντιστοιχίσουμε σε κάθε του εγγραφή έναν κόμβο του δέντρου, ξεκινώντας από τη ρίζα του δέντρου και περνώντας από κάθε επίπεδο, από αριστερά προς τα δεξιά. Με αυτή την αντιστοίχηση, μπορούν πολύ εύκολα να χρησιμοποιηθούν οι τεκμηριωμένες τεχνικές εύκολου, ασφαλούς και γρήγορου αποκλεισμού περιοχών. Ο απολογισμός της μεθόδου (θεωρητικά αλλά και πειραματικά) περιλαμβάνει θετικές και αρνητικές όψεις. Θετικές όψεις: • Το αρχείο έχει πολύ καλή απόδοση όταν διαχειριζόμαστε αντικείμενα πολλών διαστάσεων. Αυτό ήταν αναμενόμενο αφού το αρχείο λειτούργησε σαν ένα είδος VA αρχείου, όπου το ζητούμενο ήταν η δημιουργία συμπαγών γεωμετρικών προσεγγίσεων. Κι αυτό γιατί και η χρήση των οικογενειών επέφερε μία πρώτη ‘συμπίεση’ των δεδομένων αλλά και η προ-τακτοποίηση των αντικειμένων μέσω της εννοιολογικής χρήσης του δέντρου οδήγησε σε ένα είδος ομαδοποίησης γειτονικών αντικειμένων σε γειτονικές περιοχές. • Το αρχείο έχει επίσης καλές επιδόσεις και όταν διαχειριζόμαστε αντικείμενα λίγων διαστάσεων. Αυτό συμβαίνει γιατί σε σχέση με το αρχείο VA είναι αναμενόμενα καλύτερο αφού βασίζεται σε δενδρική διάταξη, ενώ για τον ίδιο λόγο είναι ανταγωνιστικό και των παραδοσιακών ιεραρχικών δέντρων. Αρνητικές όψεις: • Η στατικότητα στον ορισμό του αριθμού(ch) των παιδιών ανά κόμβο του δέντρου, δημιουργεί προβλήματα στην κατασκευή του, γιατί συνήθως οι πραγματικά όμοιες οικογένειες μπορεί είναι περισσότερες ή λιγότερες από ch. Αντιμετώπιση: Αν είναι περισσότερες, τοποθετούνται στο σύνολο των παιδιών οι ch κοντινότερες (με μικρότερες αποστάσεις από τον γονέα). Αν είναι λιγότερες, τότε ορίζεται ένα σχετικό όριο παιδιών και γεμάτων κόμβων στο δέντρο, πάνω από το οποίο τα παιδιά τοποθετούνται κανονικά στο δέντρο και οι υπόλοιποι κόμβοι μέχρι να συμπληρωθεί ο αριθμός παιδιών ch, συμπληρώνεται με κενούς κόμβους. Όταν όμως ο αριθμός των παιδιών μιας οικογένειας και οι υπόλοιποι γεμάτοι κόμβοι στο δέντρο είναι κάτω από αυτό το όριο, το αντίστοιχο προς δημιουργία δέντρο αποκόπτεται και δημιουργείται νέο μικρότερο δέντρο - με μικρότερο ch – ενώ το αρχικό δέντρο αναδιατάσσεται. Συνεπώς η τελική εφαρμογή μπορεί να περιλαμβάνει περισσότερα του ενός αρχεία Digenis, τα οποία κατά την αναζήτηση προσπελαύνονται από το μεγαλύτερο προς το μικρότερο, μέχρι να βρεθεί ομοιότητα (εάν υπάρχει). • Μπορεί να υπάρχουν απομακρυσμένες οικογένειες – να μη συνδέονται με καμία άλλη – οι οποίες δεν μπορούν να ενταχθούν σε κανένα δέντρο. Αντιμετώπιση: Δημιουργείται ένα Αρχείο Απομακρυσμένων (‘remote’ αρχείο) στο οποίο τοποθετούνται σειριακά οι απομακρυσμένες οικογένειες. Κατά την αναζήτηση αυτό το αρχείο προσπελαύνεται πρώτο, γιατί εφόσον εν γένει θα φιλοξενεί λίγες οικογένειες, η αναζήτηση σ’ αυτό θα είναι γρήγορη. Εάν υπάρχει ομοιότητα μεταξύ του αντικειμένου του ερωτήματος (query) και κάποιας οικογένειας του αρχείου, τότε έχει αποφευχθεί όλη η αναζήτηση στα δέντρα ενώ εάν πάλι δεν υπάρχει τέτοια ομοιότητα, λόγω του μικρού μεγέθους του αρχείου, η χρονική επιβάρυνση είναι σχεδόν αμελητέα. Στο τελευταίο κεφάλαιο εξετάζεται ένα είδος δυναμικής αναζήτησης ομοιότητας, το οποίο ασχολείται με τις χρονικές ακολουθίες όχι των ίδιων των αντικειμένων αλλά των πεδίων (χαρακτηριστικών) τους. Δηλαδή αυτό που ανιχνεύεται είναι το κατά πόσο μοιάζει η εξέλιξη δύο χαρακτηριστικών στο χρόνο, πληροφορία που μπορεί να σταθεί πολύ χρήσιμη σε πολλά είδη εφαρμογών (ιατρικές, οικονομικές, επιστημονικές γενικά, κλπ). Χρησιμοποιώντας ένα παράδειγμα ιατρικών δεδομένων που αφορούν ορμόνες, με τη βοήθεια της προτεινόμενης μεθόδου (Chiron) εντοπίζονται με αποδοτικό τρόπο όμοια ε / The subject of this dissertation is the invention of methods which assure effective organization and management of multi-dimensional objects in order to achieve knowledge discovery. The initial target behind this study was the needs of a demanding application intending to map the human brain in order to help the localization of epileptic foci. During the corresponding research, the Representation and Management needs of human brain data raised two core research problems:  The representation peculiarity of the composite, non-uniform, network structured three-dimensional objects(brain objects), and  The needs for effective management-use of known and derived data and knowledge dependencies, which can upgrade the application performance and dynamics. The most important part of our relative research, leaded to the: o Investigation of similarity search aspects. As this research area has great application and open problem width, it constitutes a great part of this dissertation. Taking into account that the certain geometrical and knowledge dependency features of human brain data are common – all or part of them - in many modern multimedia applications, the above problems are included in the basic Data Base research problems. Focusing our research in the above problems, we lead up to the:  Definition of new flexible data types, concepts, models, tools and data and knowledge ordering methods (Data Base BDB and models 3D-IFO and MITOS) which organize our data more flexibly and effectively, using methods that not only assure easier data access but also exploit their ‘hidden’ relationships and dependencies for more knowledge discovery.  Definition of new search trees and methods for: o Effective detection of partial similarity among multi-dimensional objects ( Lui k-n-match και INTESIS). o Obliteration of the high performance fall which occurs in similarity trees as dimensionality increases (‘dimensionality curse’) (Digenis structure ). o Detection of object features/attributes/properties (dimensions) which have similar course in the time course – for multi-dimensional objects mostly – aiming at the study and detection of possible interaction among them (Chiron proposal ). Generally, this dissertation consists of two basic parts, which refer to two research areas with great interaction: • The Multi-Dimensional Data Base Modelling • The Similarity Search among Multi-Dimensional objects. Ιn the first chapter, the problem of human brain mapping for the localization of epileptic foci is discussed. This problem raises issues related to the peculiarities of the representation and the organization of three dimensional objects with complex structures/shapes and functional dependencies and relationships among them (brain objects). In the beginning, the logical model BDB (Brain Data Base) is proposed as a first approach, introducing new entity types. In the corresponding study, a very interesting proposal is the introduction of hierarchical ordering in the Relational Model in order to organize the brain areas according to their frequencies of epileptic foci presence, improving statistically the corresponding response times. In the following, the needs of the application are studied in the basis of a Semantic – IFO model - and of an Object-oriented Model, resulting in the definition of the 3D-IFO and the MITOS (Model for the Intelligent Three-dimensional Object Support) model, respectively. In the framework of 3D-IFO model, new data types and new operators have been introduced, in order to achieve effective representation and better management of the complex brain objects. Additionally, a new constructor and the suitable attribute for its support have been introduced, in order to effectively represent the ordering among brain parts, based on a certain criterion, thus facilitating combined data retrieval. In the end, the object-oriented model MITOS, introduces a new data model (MITOS Data Model – MDM) which cooperates with an intelligent knowledge base approach (MITOS Query Language – MQL). MITOS model introduces many novelties which serve a more expressive and intelligent representation and management of multi-dimensional data and knowledge. One of these novelties constitutes the definition of one more basic object characteristic (in object-oriented theory), the relationship with the environment, releasing it from the situation or the behaviour, where its concept and representation weakens. The second MITOS novelty concerns MQL and is related to the introduction of the concept of ‘key’ in the rules area. The extension of this potentiality – the idea comes from Data Base area – leads in fact to a kind of a key, with a meaning that it could have in Knowledge Bases and can not be exactly the same with that in Data Bases, because of the specific distinctions of these two Bases. The subject of the second chapter is the detection of a least investigated similarity kind among multi-dimensional objects, the partial similarity. Partial similarity refers to similarities which are not full but they really exist. It is difficult to capture them using common techniques based on similarity functions (e.g. Euclidian distance) because these functions are affected by the whole set of object dimensions. Thus, when the objects are similar but ‘very different’ in few dimensions (e.g. very different colour and size) then the corresponding calculated functions (distances) will have very high values because of these few high dissimilarities and the similarity result will be negative while the objects will actually be similar. On the other hand, when between two objects there are low dissimilarities in most dimensions, they are actually dissimilar but the resultant function will have low value, so the dissimilar objects will be discerned as similar. In both cases, the common full similarity detection methods are not reliable. The few studies that have investigated partial similarity, have mostly focused on geometric data. The study which is extended to multi-dimensional objects in general and has led to significant results in partial similarity, is presented in a paper of Koudas and al., in VLDB 2006. It introduces the effective methods k-n-match and frequent k-n-match, which result in k objects being similar to the given ones not in all their dimensions but at least in n ones, avoiding in this way those few very dissimilar dimensions –if any- which lead to false results. Nonetheless, these methods have some weaknesses which finally result either in full similarity (when finally, in frequent k-n-match, all n’s are taken into account) or in an occasional partial similarity detection (with the suitable n’s, which should not be very high or very low, without having however any type or method to calculate the ‘best’ n’s). Based on these methods, we propose two techniques which can provably detect real partial similarities. The first of them, Lui k-n-match, succeeds in the approximate specification of the suitable n’s for the k-n-matches, based on human-computer interaction and on the suitable checks of the similar objects that k-n-matches propose. More precisely, using k-n-match, for each n a set with objects possibly similar to the given one (query object), is proposed. The user filters this set and decides which objects of the proposed set are really similar to the given one. This procedure continues until the point where, while n has become larger than d/2* , the user does not select any object as similar from the proposed object set. In this way, the results are more reliable and valid (because of human-computer interaction) while in parallel the number of the executed k-n-matches are remarkably reduced. The second partial similarity detection method (INTESIS) is based on the following observation: when two objects are similar, it usually means that they are similar in most of their characteristics. In data bases, each of object characteristic is represented by a set (usually small) of features-attributes(dimensions). Thus, if this correspondence between a characteristic and a set of attributes is defined by the developer of each application - creating dimension subsets – then the following can be successively done: a) A full similarity detection for each dimension subset b) Organization of these subsets in the corresponding hierarchical trees for their easy and effective management. The additional simplification of this choice derives from the fact that as long as the dimension subsets are small, the selection of the corresponding tree will be a very easy task, while almost all hierarchical trees have high performance for low dimensionalities. Consequently, the developer of each application can use the hierarchical tree that he/she considers as best (our proposition is R*-tree). Finally, in order to complete the procedure, the application developer has to define which is the minimum number of the requisite similar characteristics that indicate partial similarity, for the particular application. For the evaluation of the method, first of all, it is necessary to mention that it refers to a total number of dimensions less than 100 and consequently to a relatively small number of trees. As it is obvious, the final response time in a uniprocessor system is the sum of the response times of each tree. Taking into account that the number of dimensions which correspond to each tree is small, these trees have very good response times and consequently the total response time is low enough. While the use of each tree does not presuppose the use of another tree before or after it, the search in each tree can be performed in parallel. Therefore, in a multi-processing system, the total response time can be considerably reduced, achieving to reach the time needed for only one tree (when the number of processors is equal to the number of trees). Furthermore, bearing in mind that partial similarity forms a very demanding similarity search kind, not only the response times in multi-processing systems but those times in a uniprocessor system constitute satisfying performances. The third chapter studies the potentiality of defining a new structure which does not ‘suffer’ from ‘dimensional curse’, while it assures good performance for low dimensionalities too. The latest studies have resulted in the following: Although the known similarity trees (either based on space partitioning or on data partitioning perform effectively in cases of low dimensionality, their performance generally degrades as dimensionality increases (especially for more than 10 dimensions). On the other hand, VA-File constitutes a simple approximate method (it is a simple array-file of object geometric approximations) which manages to outperform any other similarity search method at high dimensionality but it has low performance for low dimensionality. In order to overcome this determinant dependence between the performance and the dimensionality of a data-object set, we propose the new hybrid structure called Digenis, which marries the logic of similarity trees with VA-Files logic. More precisely, a static parametric tree (Digenis tree) is defined in conceptual level while the Digenis file, based on Digenis tree, is used in physical level. Using this correlation, a) the similarity search procedure is located in a small part of the file, excluding most dissimilar objects from the search and b) the method is used effectively for both low and high dimensional objects, preserving generality and flexibility. The first necessary definition for Digenis proposal is related to the object families. They consist of objects having a small distance among them (based on a certain limit fl defined from the analyst, in each case) and they are represented by the ‘mean’ object of the family (if it does not exist, it is created just for this role). Each object family is hosted in a node of Digenis tree. The distance which is used is the most spread one, the Euclidian distance, for which the triangle inequality – where the method is mainly based - stands. Additionally, a second distance limit (Lt) is defined – from the analyst- which forms the limit used to conclude if two objects are similar or not. Finally, the root of the Digenis tree is the most ‘centered’ family in the total object area and the nodes being the children of it are its ch nearest families-nodes. The children of each of them are its ch nearest families, and so on. The triangle inequality which stands among the Euclidian distances of the object-families, is proved to be a very useful Theorem for the safe check exclusion of a great part of the tree , leading to a final check in a small tree area. The search analysis of the tree is very helpful for the use of Digenis file, where the real search is performed (physical level). The corresponding Digenis file in the physical level is created if each tree node composes a record of the file, beginning from the tree root and passing from each level, from left to right. Using this correspondence, the proved Digenis tree techniques of easy, safe and quick exclusion of Digenis record areas can be used. The (theoretical and experimental) evaluation of the method results in the detection of certain advantages and disadvantages of it. Advantages:  The file has very good performance for high dimensionalities. This was expected because the file works as a kind of VA-File, where the records are compact geometric approximations. This matters because both the use of object families achieves a first data ‘compression’ and the pre-arrangement of the objects via the conceptual use of the tree lead to a kind of grouping of neighboring objects in neighboring areas.  The file has also good performance for low dimensionality, because in comparison to VA-File, it is expectably better while it is based on a tree structure. For the same reason, Digenis file is competitive to the classic hierarchical similarity trees. Drawbacks:  The fact that the number of children for each node is statically defined as ch in each application is a disadvantage for the construction of the tree, because usually the really similar families may be more or less than ch. Confrontation: If the similar families of a node are more than ch, then only the ch closest to the family are placed as its children, in the next level. If they are less than ch, then a limit of children and full nodes in the tree is defined. When this limit is overcome, the nodes-children are normally placed in the tree and the rest nodes –until ch-th one – remain empty. When however the number of the children of a family and of the full nodes in the tree, are less than this limit, the corresponding subtree is separated, creating a new smaller tree – with smaller ch – while the initial tree is reorganized. Consequently, the final application may include more than one Digenis tree, which are accessed from the bigger to the smaller, until the similarity is found (if any).  Perhaps there are remote areas of object families – without any connection with other families – which can not be included in any other tree. Confrontation: A file including sequentially the remote families (called ‘remote’ file’) is created. During the similarity search, this file is the first which is accessed because while it usually hosts a few families, the search will be quick enough. If a similarity is detected (among the query object and a family in the file), then the search in the trees will be avoided while if no similarity exists, the time overhead of the file search is almost negligible, because of its size. In the last chapter, a new kind of dynamic similarity search is investigated. It is related with the time streams not of the objects themselves but of their properties/attributes/dimensions. In other words, what is detected is whether the courses of two or more properties resemble. This kind of information can be very useful for several kinds of applications (medical, financial, scientific in general, e.t.c). Using medical data related to hormonal tests as an example, we prove that, based on our method Chiron, the hormones which are developed in the same way are accurately and effectively detected. More precisely, new objects (property course objects or Chiron objects) which encode the variations of each property in certain time intervals, are defined and organized in a tree (Chiron tree). The way these objects are defined, their differences and the Chiron tree itself make its navigation and the detection of similar Chiron objects – and consequently of properties which are developed in a similar way - a quick and easy procedure. This is achieved via the distribution of the Chiron objects in the Chiron tree according to the number of the different digits that exist among them. In this way, when we search in the Chiron tree for objects similar to a given one, a simple and compact algorithm is used, which avoids a vast amount of useless checks among very different objects. Generally, the method is promising enough because it poses new problems for investigation, like the statistical analysis of its results, the search for objects that are developed in a reverse way, the management of time shifts among the property course objects and the Chiron tree optimization.

Σκοπός: Η θυμεκτομή αποτελεί κοινώς αποδεκτή θεραπεία της μυασθένειας με τις διάφορες προσπελάσεις να αναφέρονται ως ανάλογης αξίας για την επίτευξη ύφεσης της νόσου. Έχοντας πλέον την μόνιμη σταθερή ύφεση ως καθαρή και μετρήσιμη νευρολογική έκβαση των μυασθενικών ασθενών μετά θυμεκτομή και γνωρίζοντας ότι η ύφεση της νόσου αποτελεί χρόνο-εξαρτώμενο γεγονός, πραγματοποιήσαμε μια αναδρομική μελέτη των ασθενών με μυασθένεια που αντιμετωπίστηκαν χειρουργικά με σκοπό τον πιο αξιόπιστο καθορισμό του ρόλου των μεγίστων θυμικών εκτομών και την ταυτοποίηση προγνωστικών παραγόντων για ύφεση της νόσου μετά θυμεκτομή. Υλικό και μέθοδος. Η μελέτη περιλαμβάνει 78 ασθενείς που υποβλήθηκαν σε τροποποιημένη μέγιστη θυμεκτομή από το 1990 έως το 2007. Οι ενδείξεις θυμεκτομής περιελάμβαναν: οφθαλμική μυασθένεια ανθιστάμενη στη φαρμακευτική αγωγή, γενικευμένη μυασθένεια και μυασθένεια με θύμωμα. Τα στοιχεία που συλλέχθηκαν αφορούσαν τη βαρύτητα της νόσου (τροποποιημένη Osserman ταξινόμηση), την προεγχειρητική φαρμακευτική αγωγή, την ηλικία έναρξης της νόσου (≤ 40/ > 40 έτη), το χρονικό διάστημα που μεσολάβησε από τη διάγνωση στη θυμεκτομή (≤ 12/ > 12 μήνες), το φύλο, την ιστολογία του θύμου αδένα, τη θνητότητα και τις επιπλοκές. Στους ασθενείς με θύμωμα περαιτέρω στοιχεία που ελήφθησαν υπόψη αφορούσαν τον ιστολογικό τύπο του θυμώματος κατά την Παγκόσμια Οργάνωση Υγείας και το στάδιο του όγκου κατά Masaoka. Η εκτίμηση της νευρολογικής έκβασης στο τέλος του μετεγχειρητικού follow up έγινε βάση της νέας ταξινόμησης του Αμερικανικού Ιδρύματος για τη Βαρεία Μυασθένεια με την πλήρη σταθερή ύφεση να λαμβάνεται υπόψη για τον καθορισμό της επάρκειας της διενεργηθείσας εκτομής και για τη σύγκριση των αποτελεσμάτων μας με αυτά προηγουμένων μελετών. Η στατιστική ανάλυση των αποτελεσμάτων έγινε με το SPSS 17 και αφορούσε δύο ομάδες ασθενών ανάλογα με την παρουσία ή μη θυμώματος. Η μέθοδος Kaplan-Meier χρησιμοποιήθηκε για την εκτίμηση της επίπτωσης των υπό εκτίμηση προγνωστικών παραγόντων στην επίτευξη της πλήρους ύφεσης ενώ η Cox Regression ανάλυση αποτέλεσε το μοντέλο για την ανάλυση της ταυτόχρονης επίδρασης των υπό μελέτη παραμέτρων στην επίτευξη πλήρους σταθερής ύφεσης. Τιμές του p < 0.05 θεωρήθηκαν στατιστικά σημαντικές. Αποτελέσματα: 51 ασθενείς είχαν μυασθένεια χωρίς θύμωμα και 27 ασθενείς παρανεοπλασματική μυασθένεια. Δεν υπήρχαν στατιστικά σημαντικές διαφορές στα προεγχειρητικά κλινικά χαρακτηριστικά των ασθενών πλην της αναμενομένης εμφάνισης της νόσου σε απώτερη ηλικία στους ασθενείς με θύμωμα. Η θνητότητα ήταν μηδενική ενώ η χειρουργική νοσηρότητα, ανάλογη προηγουμένων μελετών θυμεκτομής με διαφορετικού τύπου προσπέλασεις, ανήλθε στο 7,7% και ήταν ως επί το πλείστον ήσσονος σημασίας. Το ποσοστό μετεγχειρητικής μυασθενικής κρίσης ήταν μόλις 3,8%. Οι ασθενείς με μυασθένεια και θύμωμα βίωσαν όψιμη νευρολογική έκβαση ανάλογη αυτής των ασθενών χωρίς θύμωμα (πιθανότητα ύφεσης 74,5% vs 85,7%, p= 0.632). Η μη χρήση στεροειδών στην προεγχειρητική φαρμακευτική αγωγή, ως έμμεσος δείκτης της βαρύτητας της νόσου, σχετίστηκε με στατιστικά καλύτερη πιθανότητα για πλήρη ύφεση των συμπτωμάτων τόσο στους ασθενείς με θύμωμα (95% CI 2.687-339.182, p= 0.006) όσο και σε αυτούς χωρίς θύμωμα (CI 95% 1.607-19.183, P= 0.007) στην πολυπαραγοντική ανάλυση. Αξιόλογη διαφορά, αν και στατιστικά μη σημαντική, για τη έκβαση της νόσου είχε η πρώιμη σε σχέση με την απώτερη χειρουργική αντιμετώπιση των ασθενών. Στη σύγκριση των 27 ασθενών με μυασθένεια και θύμωμα με 12 επιπλέον ασθενείς που υποβλήθηκαν στην ίδια επέμβαση για θύμωμα άνευ μυασθένειας η παρουσία των συμπτωμάτων μυϊκής αδυναμίας συνδυάστηκε με στατιστικά σημαντική βελτίωση της επιβίωσης των ασθενών (100% vs 38,8% στη 10ετία, p< 0.001). Στους ασθενείς με μυασθένεια χωρίς θύμωμα και απώτερης ηλικιακά έναρξης της νόσου το ποσοστό σημαντικής βελτίωσης των μυασθενικών συμπτωμάτων, εξαιρουμένης της πλήρους ύφεσης, ήταν 70%. Στους ασθενείς με μυασθένεια και θύμωμα η ιστολογική ταυτοποίηση των θυμωμάτων κατά την Παγκόσμια Οργάνωση Υγείας προέκυψε στατιστικά σημαντική τόσο στην μονοπαραγοντική όσο και στην πολυπαραγοντική ανάλυση με τα θυμώματα τύπου Β2, Α και Β3 να επιτυγχάνουν από πολύ καλή έως άριστη πιθανότητα πλήρους ύφεσης και τα θυμώματα τύπου ΑΒ, Β1 και C να έχουν απογοητευτική έκβαση όσον αφορά την ίαση. Συμπεράσματα: Η παρούσα μελέτη δείχνει ότι η τροποποιημένη μεγίστη θυμεκτομή είναι ασφαλής και σχετίζεται με υψηλή πιθανότητα για ίαση των μυασθενικών ασθενών με και χωρίς θύμωμα. Οι ασθενείς πρέπει να αντιμετωπίζονται χειρουργικά πρώιμα μετά τη διάγνωση με κυριότερο προγνωστικό παράγοντα για το απώτερο νευρολογικό αποτέλεσμα την προεγχειρητική βαρύτητα της νόσου. Η ασφαλής και πιο αξιόπιστη εκτίμηση της τελευταίας απαιτεί πιο αντικειμενικά κριτήρια όπως αυτά που θεσπίστηκαν από το Αμερικανικό Ίδρυμα για τη Βαρεία Μυασθένεια. Η ενσωμάτωση σε αυτά τα κριτήρια μοριακών παραμέτρων που φαίνεται να επηρεάζουν την πρόγνωση της νόσου, ενδεχόμενα να βελτιώσουν την αξιοπιστία της κλινικής σταδιοποίησης του MGFA και να αναδείξουν υποομάδες ασθενών με διαφορετική νευρολογική πρόγνωση μετά από θυμεκτομή. Επίσης η πρώιμη διάγνωση των θυμωμάτων εξαιτίας των συνυπαρχόντων μυασθενικών συμπτωμάτων μπορεί να οδηγήσει σε καλύτερη επιβίωση τους συγκεκριμένους ασθενείς. Τέλος η νευρολογική έκβαση των ασθενών με θυμωματώδη μυασθένεια σχετίζεται με τον ιστολογικό τύπο των θυμωμάτων, αλλά όχι αναγκαία και με την κακοήθη συμπεριφορά τους. / Objective: Thymectomy represents a widely accepted treatment for myasthenia gravis with different surgical approaches reported as comparably efficient in achieving disease’s remission. With the complete stable remission being currently accepted as a clear measurable outcome of patients with myasthenia undergoing surgical treatment and the knowledge that disease’s remission should be evaluated as a time dependent event we proceeded to a retrospective analysis of our experience on the surgical management of myasthenic patients. The objective was to access the effect of maximal resection on the neurological outcome and identify predictors of disease remission. Materials and methods: The study group consisted of 78 patients who underwent modified maximal thymectomy for myasthenia from 1990 to 2007. Indications for thymectomy included: ocular myasthenia refractory to medical treatment, generalized myasthenia and thymomatous myasthenia. The data collected included preoperative disease’s severity (modified Osserman classification), preoperative medical treatment, age at onset of the disease (≤ 40/ > 40 years), time elapsed between diagnosis and thymectomy (≤ 12/ > 12 months), gender, thymus gland histology, mortality and morbidity. In thymoma patients further analysis was carried out according the World Health Organization histological classification and the Masaoka stage of the tumors. The evaluation of the neurological outcome at the end of follow up was performed according the Myasthenia Gravis Foundation of America classification. Both the effectiveness of the resection performed and the comparison of our results with those of previous studies were done using the complete stable remission as the end point of the study. The statistical analysis of the results was carried out using the SPSS 17. Kaplan-Meier life table analysis was performed and the log rank test was used to evaluate the effect of the variables examined on the distribution of disease’s remission over time. The Cox proportional hazard model was also applied to verify the concurrent effect of the evaluated factors on the achievement of complete stable remission. P values < 0.05 were considered statistically significant. Results: 51 patients suffered of non thymomatous myasthenia while 27 patients had myasthenia with thymoma. The two groups were comparable in refer to the clinical features of the patients apart the more advanced age at the time of the diagnosis for thymoma patients. There was no perioperative mortality, while the surgical morbidity was comparable to the one reported in other series of patients with different surgical approaches and was 7.7%. The rate of postoperative myasthenic crisis was only 3.8%. Thymoma and non thymoma patients experienced comparable complete stable remission prediction (74.5% vs 85.7% at 15 years, p= 0.632). The absence of steroids in the preoperative medical regimen was statistically associated with the achievement of complete stable remission in both thymoma (95% CI 2.687-339.182, p= 0.006) and non thymoma patients (CI 95% 1.607-19.183, P= 0.007) in multivariate analysis. There was an important difference, although not statistically significant, for the neurological outcome between early and late surgical treatment. When the 27 patients with myasthenia and thymoma were compared with other 12 patients similarly operated for thymoma without symptoms and signs of muscular weakness we found that the presence of myasthenia was statistically associated with improved survival (100% vs 38.8% at 10 years, p< 0.001). Non thymoma patients presenting with late onset myasthenia, experienced high improvement (complete stable remission excluded) rate reaching up to 70% at the end of follow up. Among patients with thymomatous myasthenia gravis the World Health Organization histological classification was statistically associated with the late neurological outcome. Thymoma types A, B3 and B2 reached a high to excellent prediction of disease’s remission while types AB, B2 and C had a disappointing neurological outcome. Conclusons: The present study demonstrated that the modified maximal thymectomy is a safe procedure, associated with an excellent neurological outcome in both thymomatous and non thymomatous myasthenia. The patients should be operated early after the diagnosis is made with the disease’s severity being the prime determinant of the possibility to achieve complete remission of myasthenic symptoms. The evaluation of disease’s severity requires objective criteria like the ones proposed by the Myasthenia Gravis Foundation of America. The inclusion in these criteria of molecular markers related to myasthenia’s prognosis and its neurological outcome after thymectomy may further enhance its validity and may allow the identification of subgroups of patients with different disease prognosis after thymectomy. The presence of muscular weakness may lead to early diagnosis and surgical treatment of thymomas with improved survival. Finally the neurologic outcome in thymoma patients after thymectomy may be statistically associated with the World Health Organization classification subtypes but not necessarily with the aggressiveness of these tumors.

Στην εργασία, αυτή, εξετάζονται οι μέθοδοι συμπίεσης του συνόλου δοκιμής με τη χρήση πινάκων που έχουν ήδη προταθεί και προτείνεται μία νέα μέθοδος συμπίεσης δεδομένων δοκιμής για πυρήνες που ο έλεγχος ορθής λειτουργίας υλοποιείται μέσω μονοπατιών ολίσθησης. Η νέα μέθοδος επαναχρησιμοποιεί μπλοκ του πίνακα για τη σύνθεση διανυσμάτων δοκιμής. Δύο νέοι αλγόριθμοι παρουσιάζονται για επιλεκτική και πλήρη καταχώρηση τμημάτων του συνόλου δοκιμής σε πίνακα. Η προτεινόμενη μέθοδος συγκρίνεται με τις υπάρχουσες μεθόδους ως προς το ποσοστό συμπίεσης αλλά και ως προς το κόστος υλοποίησης. Για την αξιολόγηση της μεθόδου λαμβάνονται υπόψη σύνολα δοκιμής που έχουν παραχθεί για την ανίχνευση απλών σφαλμάτων μόνιμης τιμής, απλών σφαλμάτων μόνιμης τιμής με πολλαπλότητα ανίχνευσης Ν (Ν-detect) και σφαλμάτων καθυστέρησης μετάβασης. / In this work we refer to dictionary based test data compression methods. At first the already known dictionary based test data compression methods are comparably presented. Then we propose a new method and we show that the test data compression achieved by a dictionary based method can be improved significantly by suitably reusing parts of the dictionary entries. To this end two new algorithms are proposed, suitable for partial and complete dictionary coding respectively. For the evaluation of the proposed method, test sets have been generated and used based on the stuck-at fault model for single and N detection of each fault as well as on the transition fault model.

Το θέμα της παρούσας μεταπτυχιακής διπλωματικής εργασίας είναι η εφαρμογή της θεωρίας των Σχεδόν Πλήρως Αναλυόμενων Στοχαστικών Συστημάτων (Nearly Completely Decomposable) σε μία σειρά προβλημάτων στα οποία παραδοσιακές προσεγγίσεις αποδεικνύονται ερμηνευτικά στείρες και υπολογιστικά κοστοβόρες. Στο πρώτο μέρος της διπλωματικής αφού κάνουμε μία διαισθητικού τύπου παρουσίαση της ιδέας της decomposability και συνοψίσουμε τα απαραίτητα στοιχεία του θεωρητικού υποβάθρου που χρησιμοποιούμε στα πλαίσια της εργασίας, παραθέτουμε τονπυρήνα της θεωρίας της decomposability, όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία. Τέλος, παραθέτουμε και μία υλοποίηση του KMS αλγορίθμου Συσσωμάτωσης/Αποσυσσωμάτωσης, για τη λύση NCD συστημάτων. Το δεύτερο μέρος του συγγράμματος, είναι αφιερωμένο στην εφαρμογή της NCD σε δύο ενδιαφέροντα προβλήματα εκτίμησης απόδοσης υπολογιστικών συστημάτων. Συγκεκριμένα, μελετούμε μία ιδιότυπη ουρά που εξυπηρετεί πελάτες διαφορετικών κλάσεων, με τις ανά κλάση αφίξεις να χαρακτηρίζονται από εναλλαγές μεταξύ περιόδων ηρεμίας και κινητικότητας και την εξυπηρέτηση να γίνεται σε δέσμες πελατών της ίδιας κλάσης. Το κίνητρο για τη μελέτη αυτής της ουράς εντοπίζεται στη bursty φύση της μεταγωγής πακέτων στα σύγχρονα δίκτυα αλλά και στους reassembly buffers των multicluster πολυεπεξεργαστικών συστημάτων. Η ανάλυση της ουράς με παραδοσιακές τεχνικές οδηγεί αναπόφευκτα σε μαρκοβιανή αλυσίδα πολύ μεγάλου χώρου κατάστασης. Εμείς, ξεκινάμε από το πλήρες στοχαστικό μητρώο και αφού διαμερίσουμε κατάλληλα το χώρο καταστάσεων, αποδεικνύουμε ικανές συνθήκες υπό τις οποίες το αρχικό σύστημα είναι δυνατόν να αναλυθεί σε πολλαπλά επίπεδα υποσυστημάτων, η αυτόνομη ανάλυση των οποίων δίνει μία πολύ καλή προσέγγιση της στάσιμης κατανομής του αρχικού συστήματος. Επίσης, παραθέτουμε και αποδεικνύουμε μία ικανή συνθήκη για μηδενικό σφάλμα προσέγγισης και την ερμηνεύουμε σε όρους προδιαγραφών του προβλήματος. Τέλος, θεωρούμε μία ειδική συμμετρική εκδοχή για την οποία καταφέρνουμε να δώσουμε μία κλειστή έκφραση της κατανομής πληρότητας της ουράς συναρτήσει της λύσης των υποσυστημάτων. Για να δείξουμε την απλοποίηση της ανάλυσης που επιφέρει η χρήση του NCD μοντέλου θεωρούμε ένα σενάριο για το οποίο προχωρούμε την ανάλυση σε βάθος και καταφέρνουμε να εξάγουμε χρήσιμες μετρικές στις οποίες, σε αντίθετη περίπτωση, θα ήταν ιδιαίτερα επίπονο να καταλήξει κανείς. Συγκεκριμένα, υπολογίζουμε την πιθανότητα blocking και δείχνουμε πως αυτή μειώνεται σχεδόν εκθετικά με το μέγεθος της ουράς. Βλέπουμε τελικά πως η εκμετάλλευση της NCD ιδιότητας από τη μία διευκολύνει την ανάλυση και από την άλλη παρέχει ανεκτίμητη διαίσθηση σχετικά με τη μεταβατική συμπεριφορά του συστήματος προς την κατάσταση στατιστικής ισορροπίας. Το δεύτερο μέρος της διπλωματικής κλείνει με τη μελέτη κριτηρίων υπό τα οποία, πολυεπεξεργαστικά συστήματα που χωρίζονται σε ομάδες ισχυρά αλληλεπιδρώντων επεξεργαστών, μπορούν να αναλυθούν με χρήση της θεωρίας NCD. Είναι γνωστό πως στα δίκτυα ουρών αναμονής συγκρίσιμων ρυθμών εξυπηρέτησης, η NCD του μητρώου πιθανοτήτων δρομολόγησης συνεπάγεται την NCD του δικτύου. Εμείς, θεωρούμε μία ειδική περίπτωση τέτοιων συστημάτων για την οποία δείχνουμε ένα, εύκολο να ελεγχθεί, κριτήριο για NCD. Τέλος, εξετάζουμε βαθύτερα το σφάλμα της προσέγγισης, και χρησιμοποιώντας ένα πρόσφατο αποτέλεσμα της θεωρίας των σχεδόν ασύζευκτων μαρκοβιανών αλυσίδων δίνουμε έναν επιπλέον ποιοτικό περιορισμό που πρέπει να ικανοποιούν τα εν λόγω συστήματα για να πάρει κανείς ικανοποιητική προσέγγιση από την ανάλυσή τους σε ανεξάρτητα block. Στο τρίτο μέρος της παρούσας εργασίας, εξετάζουμε την εφαρμογή της NCD στο πρόβλημα της κατάταξης ιστοσελίδων. Η πρόσφατη έρευνα έχει σχολιάσει την ειδική δομή του στοχαστικού μητρώου που προκύπτει από το γράφο του διαδικτύου· συγκεκριμένα, οι τοπολογικές ιδιότητες της αυτοoργάνωσης του Ιστού φαίνεται να παράγουν ένα στοχαστικό μητρώο με NCD δομή. Εμείς, αφού παραθέσουμε μία σύνοψη των μαθηματικών πίσω από τον αλγόριθμο PageRank, σχολιάζουμε και δικαιολογούμε διαισθητικά την NCD δομή του Ιστού αλλά και τη φύση των υποσυστημάτων. Τέλος, προτείνουμε έναν νέο αλγόριθμο κατάταξης με το όνομα NCDawareRank, o οποίος εκμεταλλεύεται την NCD ιδιότητα για να πετύχει ποιοτικότερο και ταχύτερο ranking. Μάλιστα, δίνουμε δύο εκδοχές του αλγορίθμου, μία σειριακή και μία παράλληλη, η οποία εκμεταλλεύεται την NCD του Ιστού και υπολογιστικά. Τα οφέλη που υπόσχεται ο NCDawareRank τα επιβεβαιώνουμε και πειραματικά εκτελώντας μία σειρά από πειράματα τόσο σε τεχνητά όσο και σε πραγματικά δεδομένα, αντιπαραβάλλοντας τα αποτελέσματα μας με αυτά του αλγορίθμου PageRank. O NCDawareRank φαίνεται μάλιστα να δίνει λύση σε ένα γνωστό πρόβλημα του PageRank: αυτό της μεροληψίας εναντίον νεοεισερχομένων σελίδων. Άλλο ένα, τέλος, παράπλευρο όφελος του αλγορίθμου NCDawareRank είναι αυτό της Levelwise κατάταξης, η οποία εκτός της σημασίας που έχει αφεαυτής, μπορεί να υποδείξει εξυπνότερο crawling ή ακόμα και αποδοτικότερα σχήματα ευρετηριοποίησης του Ιστού. Στο τέταρτο και τελευταίο μέρος της διπλωματικής εφαρμόζουμε την NCD στην εύρεση των στοχαστικά ευσταθών καταστάσεων μίας κατηγορίας εξελικτικών παιγνίων στα οποία εμφανίζονται πολυεπίπεδες στρατηγικές δυναμικές. Αφού παραθέσουμε κάποιες πρόσφατες παρατηρήσεις από τη βιβλιογραφία της οικονομετρίας σχετικά με την αξιοποίηση της NCD στην προσεγγιστική ανάλυσή τους, αποδεικνύουμε συνθήκες υπό τις οποίες είναι δυνατόν να πετύχει κανείς ακριβή ανάλυση. / The purpose of this master’s thesis is the application of the theory of Nearly Completelely Decomposable stochastic systems to a number of interesting problems for which tra- ditional techniques turn out to be both intuitively unappealing and computationally in- tractable. In the first part of this work, after introducing, the concept of decomposability in an intuitive way and summarizing the essential elements of the theoretical background that is necessary to follow the rest of the text, we present the fundamental mathematical principles of NCD as established by Courtois in his classic monograph. Finally, we give an implementation of the KMS iterative aggregation/disaggregation algorithm which is commonly used for the solution of NCD systems. The second part of the dissertation is devoted to the application of NCD to two inter- esting problems of Computer Systems Performance Evaluation. Specifically, we study an uncommon discrete time queue that serves customers from different classes, with the ar- rivals of each class characterized by alternating busy and idle periods. The service is done in batches of customers of the same class. The motivation behind the study of this queue, lies in the bursty nature of packet switching, as well as in the modern reassembly buffers of multicluster multiprocessor systems. The traditional analysis techniques of this queue inevitably lead to Markov chains with very large state space. We begin with the complete stochastic matrix and after careful partitioning of the state space, we give sufficient condi- tions under which the original system can be analysed through multi level decomposition into subsystems, the autonomous analysis of which results in a very good approximation to the stationary distribution of the original system. Furthermore, we present and prove a sufficient condition for an error-free approximation and we give an interpretation of this condition in terms of the specifications of the problem. Finally, we consider a special sym- metric version of the problem, for which we manage to derive a closed-form expression for the queue’s occupancy distribution as a function of the steady state probabilities of the subsystems. To demonstrate the simplification of the analysis brought by the NCD model, we con- sider a scenario in which we proceed to an in depth analysis and we manage to extract useful metrics the derivation of which, would be considerably harder without exploiting 13 Abstract 14 NCD. Specifically, we calculate the blocking probability and we show that it decreases almost exponentially with the size of the queue. From our analysis, it is clear that the exploitation of the NCD model increases significantly our ability to understand the dy- namics of our system and to interpret aspects of its transient behaviour towards statistical equilibrium. The second part of this work ends with the study of criteria under which multipro- cessing systems, that can be divided into groups of strongly interacting processors, can be analysed using the theory of NCD. It is known that in queueing networks with servers of comparable service rates, the NCD of the routing probability matrix implies the NCD of the network. We consider a special case of such systems and we derive an easy to check criterion for NCD. Finally, we look deeper into the error analysis of this approach, and using a recent result from the theory of nearly uncoupled Markov chains, we give an addi- tional qualitative constrain to be met by these systems in order to get a good approximation of their analysis into independent blocks. In the third part of this paper, we examine the application of NCD to the problem of ranking websites. Recent research has commented on the special structure of the stochastic matrix which corresponds to the web-graph. In particular, the topological properties of the Web seems to produce a NCD stochastic matrix. Here, after presenting briefly the mathe- matical basis of PageRank, we give a linear algebraic as well as an intuitive justification of the NCD Web structure and we discuss the nature of the subsystems. Finally, we propose a new ranking algorithm named NCDawareRank, which exploits NCD in order to achieve a fairer and faster ranking. Indeed, we give two versions of the algorithm, one serial and one parallel, in which we take advantage of the computational benefits of NCD as well. The advantages of NCDawareRank are then confirmed experimentally through a series of tests on both, artificial and real data. NCDawareRank seems to solve a known problem of PageRank: the bias against new websites. Finally, another side benefit of our algorithm is that it makes it easy to extract a level-wise ranking, which besides its importance in itself, may indicate smarter crawling or even more sophisticated and efficient indexing schemes of the Web. Finally, in the fourth part of this work we apply NCD to the problem of finding the stochastically stable states of a class of evolutionary games which involve multilevel strategic dynamics. After presenting some interesting recent results coming from the lit- erature of econometrics, we give conditions under which it is possible to get the exact stochastically stable states through the use of NCD.