Les bases de données répliquées cohérentes à terme récentes encapsulent la complexité de la concurrence et des pannes par le biais d'une interface supportant la cohérence causale, protégeant l'application des problèmes d'ordre, et/ou des Types de Données Répliqués (RDTs), assurant une sémantique convergente des mises-à-jour concurrentes en utilisant une interface objet. Cependant, les algorithmes fiables pour les RDTs et la cohérence causale ont un coût en terme de taille des métadonnées. Cette thèse étudie la conception de tels algorithmes avec une taille de métadonnées minimisée et leurs limites. Notre première contribution est une étude de la complexité des métadonnées des RDTs. Les nombreuses implémentations existantes impliquent un important surcoût en espace de stockage. Nous concevons un ensemble optimisé et un registre RDTs avec un surcoût des métadonnées réduit au nombre de répliques. Nous démontrons également les bornes inférieures de la taille des métadonnées pour six RDTs, prouvant ainsi l'optimalité de quatre implémentations. Notre seconde contribution est le design de SwiftCloud, une base de données répliquée causalement cohérente d'objets RDTs pour les applications côté client. Nous concevons des algorithmes qui supportent un grand nombre de répliques partielles côté client, s'appuyant sur le cloud, tout en étant tolérant aux fautes et avec une faible taille de métadonnées. Nous démontrons comment supporter la disponibilité (y compris la capacité à basculer entre des centre de données lors d'une erreur), la cohérence et le passage à l'échelle (petite taille de métadonnées, parallélisme) au détriment d'un léger retard dans l'actualisation des données. / Eventually consistent replicated databases offer excellent responsiveness and fault-tolerance, but expose applications to the complexity of concurrency andfailures. Recent databases encapsulate these problems behind a stronger interface, supporting causal consistency, which protects the application from orderinganomalies, and/or Replicated Data Types (RDTs), which ensure convergent semantics of concurrent updates using object interface. However, dependable algorithms for RDT and causal consistency come at a cost in metadata size. This thesis studies the design of such algorithms with minimized metadata, and the limits of the design space. Our first contribution is a study of metadata complexity of RDTs. RDTs use metadata to provide rich semantics; many existing RDT implementations incur high overhead in storage space. We design optimized set and register RDTs with metadata overhead reduced to the number of replicas. We also demonstrate metadata lower bounds for six RDTs, thereby proving optimality of four implementations. Our second contribution is the design of SwiftCloud, a replicated causally-consistent RDT object database for client-side applications. We devise algorithms to support high numbers of client-side partial replicas backed by the cloud, in a fault-tolerant manner, with small metadata. We demonstrate how to support availability and consistency, at the expense of some slight data staleness; i.e., our approach trades freshness for scalability (small metadata, parallelism), and availability (ability to fail-over between data centers). We validate our approach with experiments involving thousands of client replicas.

Η γλώσσα Java έχει πλέον εδραιωθεί σαν μια από τις πιο συχνά χρησιμοποιούμενες γλώσσες όχι μόνο λόγω της εξαιρετικής υποστήριξης σύγχρονων παραδειγμάτων προγραμματισμού, όπως ο αντικειμενοστραφής και ο γενικευμένος προγραμματισμός, αλλά κυρίως λόγω της εύκολης μεταφερσιμότητας του κώδικα και της ανεξαρτησίας που παρέχει στα προγράμματά της από κάποια συγκεκριμένη πλατφόρμα υλικού-λειτουργικού συστήματος. Η δυνατότητα αυτή συνοψίζεται στο σύνθημα “Write once, run anywhere” που καθιέρωσε η Sun, η εταιρία η οποία σχεδίασε αρχικά την γλώσσα. Κάτι τέτοιο, επιτυγχάνεται με την μετάφραση ενός προγράμματος από πηγαίο κώδικα Java σε μια ενδιάμεση αναπαράσταση object κώδικα (bytecode), η οποία στη συνέχεια εκτελείται στα πλαίσια μιας εικονικής μηχανής. Η πατροπαράδοτη μέθοδος εκτέλεσης των προγραμμάτων από την εικονική μηχανή ακολουθεί το μοντέλο της διερμήνευσης (interpretation), το οποίο στην πράξη δεν είναι καθόλου αποδοτικό, σε ότι αφορά το χρόνο εκτέλεσης. Μια διαφορετική προσέγγιση στην εκτέλεση Java bytecode είναι αυτή της δυναμικής μετάφρασης (Just In Time compilation – JIT compilation). Εδώ, την πρώτη φορά που εμφανίζεται η ανάγκη να εκτελεστεί ένα συγκεκριμένο τμήμα κώδικα, η εικονική μηχανή το επεξεργάζεται, εφαρμόζοντας προαιρετικά μετασχηματισμούς βελτιστοποίησης και παράγει τον αντίστοιχο κώδικα για το συγκεκριμένο σύστημα-οικοδεσπότη στο οποίο εκτελείται και η ίδια. Ο κώδικας αυτός στη συνέχεια μπορεί να επαναχρησιμοποιηθεί, εξαλείφοντας το κόστος της επαναληπτικής μετάφρασης του ίδιου τμήματος bytecode και μειώνοντας το συνολικό χρόνο εκτέλεσης. Στο πλαίσιο της συγκεκριμένης μεταπτυχιακής εργασίας κατασκευάζουμε ένα JIT μεταφραστή για μια εικονική μηχανή ειδικού σκοπού, το DSJOS (Distributed Scalable Java Operating System). Όπως φανερώνει και το όνομα του, το DSJOS είναι ουσιαστικά ένα κατανεμημένο σύστημα που προσφέρει στα προγράμματα που εκτελούνται εντός αυτού την αφαίρεση μιας Java εικονικής μηχανής. Ο JIT που δημιουργούμε χρησιμοποιεί ως εσωτερική αναπαράσταση το Ιεραρχικό Γράφημα Εργασιών (Hierarchical Task Graph – HTG) και στηρίζεται στη βιβλιοθήκη μετασχηματισμών και βελτιστοποιήσεων (compilation framework) PROMIS. Η υλοποίηση μας διαρθρώνεται σε τρία κυρίως στάδια: το frontend το οποίο είναι υπεύθυνο για την μετατροπή Java bytecode στην ενδιάμεση αναπαράσταση, το backend που μετατρέπει την ενδιάμεση αναπαράσταση σε κώδικα μηχανής για συστήματα x86 και, τέλος, το επίπεδο χρόνου εκτέλεσης που παρέχει στα εκτελούμενα προγράμματα διάφορες υπηρεσίες απαραίτητες για την εκτέλεση του (π.χ. διαχείριση εξαιρέσεων). Παράλληλα με το σχεδιασμό του βασικού μεταφραστή και την ενσωμάτωση του στο DSJOS, σχεδιάζουμε και υλοποιούμε και ένα σύνολο μετασχηματισμών, τόσο στο frontend όσο και στο backend, οι οποίοι έχουν ως σκοπό να βελτιώσουν την ποιότητα του παραγόμενου κώδικα και να μειώσουν το χρόνο εκτέλεσης των προγραμμάτων. / -

Οι Δομές Δεδομένων είναι ένας από τους σημαντικότερους και ιστορικότερους κλάδους της Επιστήμης των Υπολογιστών, με συνεχή εξέλιξη από τη δεκαετία του εβδομήντα μέχρι σήμερα, παρέχοντας λύσεις σε θεμελιώδη προβλήματα σε ταξινόμηση, οργάνωση, διαχείριση και αναζήτηση πληροφορίας. Παράλληλα, η ανάπτυξη σύγχρονων κλάδων της Επιστήμης των Υπολογιστών όπως τα Σύγχρονα, Δικτυοκεντρικά Πληροφοριακά Συστήματα και η Βιοπληροφορική, έφερε μαζί της την έκρηξη των δεδομένων. Η ανάγκη αποδοτικής διαχείρισης της παρεχόμενης πληροφορίας καθίσταται έτσι πιο επιτακτική από ποτέ. Στα πλαίσια αυτής της διατριβής αναγνωρίζοντας την ανάγκη για αποδοτική διαχείριση πληροφορίας σε όλα τα επίπεδα, παρουσιάζουμε τη μελέτη και την πρόταση λύσεων σε σύγχρονα προβλήματα στους χώρους: της Διαχείρισης Συμβολοσειρών, της Αναδιοργάνωσης Δικτυακών Τόπων, της Ανακάλυψης 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.

Comprendre la genèse d’une situation de conduite requiert d’analyser les choixfaits par le conducteur au volant de son véhicule pendant l’activité de conduite, dans sacomplexité naturelle et dans sa dynamique située. Le LESCOT a développé le modèleCOSMODRIVE, fournissant un cadre conceptuel pour la simulation cognitive de l’activitéde conduite automobile. Pour exploiter ce modèle en simulation, il est nécessairede produire les connaissances liées à la situation de conduite sous forme d’un automatepar exemple. La conception d’un tel automate nécessite d’une part de disposer de donnéesissues de la conduite réelle, enregistrées sur un véhicule instrumenté et d’autrepart d’une expertise humaine pour les interpréter.Pour accompagner ce processus d’ingénierie des connaissances issues de l’analysed’activité, ce travail de thèse propose une méthode de découverte interactive deconnaissances à partir de traces d’activité. Les données de conduite automobile sontconsidérées comme des M-Traces, associant une sémantique explicite aux données,exploitées en tant que connaissances dans un Système à Base de Traces (SBT). Le SBTpermet de filtrer, transformer, reformuler et abstraire les séquences qui serviront à alimenterla synthèse de modèles automates de l’activité de conduite. Nous reprenons destechniques de fouille de workflow permettant de construire des automates (réseaux dePetri) à partir de logs. Ces techniques nécessitent des données complètes ou statistiquementreprésentatives. Or les données collectées à bord d’un véhicule en situationde conduite sont par nature des cas uniques, puisqu’aucune situation ne sera jamaisreproductible à l’identique, certaines situations particulièrement intéressantes pouvanten outre être très rarement observées. La gageure est alors de procéder à une forme degénéralisation sous la forme de modèle, à partir d’un nombre de cas limités, mais jugéspertinents, représentatifs, ou particulièrement révélateurs par des experts du domaine.Pour compléter la modélisation de telles situations, nous proposons donc de rendreinteractifs les algorithmes de synthèse de réseau de Petri à partir de traces, afin depermettre à des experts-analystes de guider ces algorithmes et de favoriser ainsi la découvertede connaissances pertinentes pour leur domaine d’expertise. Nous montreronscomment rendre interactifs l’algorithme α et l’algorithme α+ et comment généralisercette approche à d’autres algorithmes.Nous montrons comment l’utilisation d’un SBT et de la découverte interactived’automates impacte le cycle général de découverte de connaissances. Une méthodologieest proposée pour construire des modèles automates de l’activité de conduiteautomobile.Une étude de cas illustre la méthodologie en partant de données réelles de conduiteet en allant jusqu’à la construction de modèles avec un prototype logiciel développédans le cadre de cette thèse / Driving is a dynamic and complex activity. Understanding the origin of a driving situationrequires the analysis of the driver’s choices made while he/she drives. In addition,a driving situation has to be studied in its natural complexity and evolution. LESCOThas developed a model called COSMODRIVE, which provides a conceptual frameworkfor the cognitive simulation of the activity of car driving. In order to run themodel for a simulation, it is necessary to gather knowledge related to the driving situation,for example in the form of an automaton. The conception of such an automatonrequires : 1) the use of real data recorded in an instrumented car, and, 2) the use of humanexpertise to interpret these data. These data are considered in this thesis as activitytraces.The purpose of this thesis is to assist the Knowledge Engineering process of activityanalysis. The present thesis proposes a method to interactively discover knowledgefrom activity traces. For this purpose, data from car driving are considered as M-traces– which associate an explicit semantic to these data. This semantic is then used asknowledge in a Trace Based System. In a Trace Based System, M-traces can be filtered,transformed, reformulated, and abstracted. The resulting traces are then used as inputsin the production of an automaton model of the activity of driving. In this thesis,Workflow Mining techniques have been used to build automata (Petri nets) from logs.These techniques require complete or statistically representative data sets. However,data collected from instrumented vehicles are intrinsically unique, as no two drivingsituations will ever be identical. In addition, situations of particular interest, such ascritical situations, are rarely observed in instrumented vehicle studies. The challenge isthen to produce a model which is a form of generalisation from a limited set of cases,which have been judged by domain experts as being relevant and representative of whatactually happens.In the current thesis, algorithms synthesising Petri nets from traces have been madeinteractive, in order to achieve the modelling of such driving situations. This thenmakes it possible for experts to guide the algorithms and therefore to support the discoveryof knowledge relevant to the experts. The process involved in making the α-algorithm and the α+-algorithm interactive is discussed in the thesis in a way that canbe generalised to other algorithms.In addition, the current thesis illustrates how the use of a Trace Based System andthe interactive discovery of automata impacts the global cycle of Knowledge Discovery.A methodology is also proposed to build automaton models of the activity of cardriving. Finally, a case study is presented to illustrate how the proposed methodologycan be applied to real driving data in order to construct models with the softwaredeveloped in this thesis