Εξατομικευμένη, σημασιολογική και διερευνητική ανάλυση δεδομένων

Abstract

In the Big Data era, systems in several application areas face significant efficiency and effectiveness challenges, due to the ever increasing Volume, Variety and Velocity of data. In this context, systems have to handle vast amounts of data in real time and operate in environments where different users, working on different scenarios, generate, explore and analyse different forms of data. To this direction, this thesis studies the development of personalization, exploration and semantic techniques for facilitating Big Data management and analysis. Specifically, we propose methods for: (a) scalable preference-aware data management and analysis; (b) efficient exploration and visualization over large datasets; and (c) semantic data integration, exploration and retrieval.In the context of personalized data analysis, we study the following problems. First, we study the problem of finding and ranking objects that are preferable by a group of users based on their preferences. We propose an objective and fair interpretation of this problem. Based on this interpretation, we develop efficient index-based algorithms and we introduce an objective ranking scheme satisfying several theoretical properties. In the next problem, we thoroughly study the performance of some of the most well-known external memory skyline algorithms. Particularly, the considered algorithms are redesigned following a formal external memory model. Then, we propose numerous different design choices and we study the resulted algorithms' variations.Regarding exploratory data analysis two problems are considered. In the first one we handle efficient on-the-fly visual exploration over large sets of data. For this problem we propose a multilevel framework that exploits a tree-based structure to hierarchically aggregate objects. Considering different exploration scenarios, we enable efficient exploration via incremental hierarchy construction and prefetching based on user interaction. Further, we provide on-the-fly efficient adaptation of the hierarchies based on user preferences. The second problem considers the exploration and visualization of very large graphs. We propose a new paradigm that allows efficient large graph visual exploration, similar to the exploration paradigm used in maps. Also, we present a disk-based scheme in order to index and store the visualized graph. In this setting, user's interactions are translated to efficient spatial operations. Finally, in order to visualize very large graphs, a partition-based visualization approach is introduced.With respect to semantic data analysis, we focus on three problems. The first problem regards the integration between XML and Semantic Web. We present an interoperability framework that bridges the heterogeneity gap by exploiting a model for the expression of OWL-RDF/S to XML Schema mappings, a method for SPARQL to XQuery translation, and model which transforms XML Schemas into OWL ontologies. The second problem regards the use of semantics in document annotation and retrieval. For this problem we propose a semantic-based annotation model, as well as a learning method for recommending annotations. Finally, we introduce an effective retrieval method that enriches information retrieval techniques with semantics. In the last problem, we study the modelling and the exploration of evolving data, adopting the Linked Data paradigm. As a result, we propose a RDF-based change model and we develop a Linked Data infrastructure that allows exploration and retrieval over evolving data.

Στην εποχή των Μεγάλων Δεδομένων, τα συστήματα αντιμετωπίζουν σημαντικές προκλήσεις που σχετίζονται με την αποδοτικότητα και την αποτελεσματικότητα τους. Οι προκλήσεις αυτές απορρέουν κυρίως από τον Όγκο, την Ετερογένεια και την Ταχύτητα που χαρακτηρίζει τα δεδομένα σήμερα. Σε αυτό το πλαίσιο, τα σημερινά συστήματα πρέπει σε πραγματικό χρόνο να διαχειρίζονται μεγάλους όγκους δεδομένων, καθώς και να λειτουργούν σε περιβάλλοντα όπου διαφορετικοί χρήστες οι οποίοι εργάζονται σε διάφορα σενάρια, δημιουργούν, διερευνούν και αναλύουν ποικίλες μορφές δεδομένων. Προς την κατεύθυνση αυτή, η παρούσα διατριβή μελετά την ανάπτυξη εξατομικευμένων, διερευνητικών και σημασιολογικών τεχνικών για την διαχείριση και ανάλυση Μεγάλων Δεδομένων. Πιο συγκεκριμένα, προτείνονται μέθοδοι για: (α) κλιμακούμενη διαχείριση και ανάλυση δεδομένων βασισμένη σε προτιμήσεις χρηστών (β) αποδοτική διερεύνηση και οπτικοποίηση μεγάλων συνόλων δεδομένων και (γ) σημασιολογική ολοκλήρωση, διερεύνηση και ανάκτηση δεδομένων.Όσον αφορά στο πρώτο μέρος εργασιών, αντικείμενο έρευνας αποτέλεσε η εξατομικευμένη ανάλυση δεδομένων, όπου μελετήθηκαν τα ακόλουθα προβλήματα. Αρχικά μελετάται το πρόβλημα της εύρεσης και ταξινόμησης αντικείμενων τα οποία θεωρούνται προτιμητέα από μια ομάδα χρηστών, με βάση τις προτιμήσεις τους. Αποτέλεσμα της μελέτης, είναι η διατύπωση μιας αντικειμενική και δίκαιης ερμηνεία αυτού του προβλήματος. Με βάση αυτή την ερμηνεία, αναπτύχθηκαν αποδοτικοί αλγόριθμοι βασισμένοι σε ευρετήρια και προτάθηκε ένα σχήμα αντικειμενικής ταξινόμησης, το οποίο ικανοποιεί αρκετές θεωρητικές ιδιότητες. Σε επόμενο πρόβλημα, πραγματοποιήθηκε εκτεταμένη μελέτη και σύγκριση τεχνικών αποτίμησης ερωτημάτων κορυφογραμμής σε δευτερεύουσας μνήμη. Πιο συγκεκριμένα, ένα σύνολο αλγορίθμων κορυφογραμμής μοντελοποιήθηκαν και υλοποιήθηκαν σύμφωνα με το μοντέλο εξωτερικής μνήμης. Επιπλέον, για τους υπό εξέταση αλγόριθμους προτείνεται ένα σύνολο παραλλαγών. Η εκτεταμένη πειραματική μελέτη ανέδειξε νέα συμπεράσματα σχετικά με την σχεδίαση και την απόδοση των αλγορίθμων κορυφογραμμής.Στο δεύτερο μέρος εργασιών, του οποίου αντικείμενο έρευνας αποτέλεσε η διερευνητική ανάλυση δεδομένων, μελετήθηκαν δυο προβλήματα. Πιο συγκεκριμένα, μελετήθηκε το πρόβλημα της αποδοτικής και άμεσης οπτικής διερεύνησης σε μεγάλα σύνολα δεδομένων. Αποτέλεσμα της μελέτης, είναι η ανάπτυξη ενός πλαισίου πολλαπλών επιπέδων βασιζόμενο σε μια δεντρική δομή η οποία πραγματοποιεί την ιεραρχική ομαδοποίηση των δεδομένων. Λαμβάνοντας υπόψη διαφορετικά σενάρια διερεύνησης, το πλαίσιο επιτρέπει την αποδοτική διερεύνηση μέσω της σταδιακής κατασκευής της ιεραρχίας, η οποία βασίζεται στην αλληλεπίδραση του χρήστη. Επιπλέον, περιγράφεται μια μέθοδος η οποία παρέχει αποδοτική και άμεση προσαρμογή των ιεραρχιών με βάση τις προτιμήσεις του χρήστη. Τέλος, παρουσιάζεται μια εκτεταμένη θεωρητική και πειραματική ανάλυση. Στο δεύτερο πρόβλημα μελετάται η διερεύνηση και οπτικοποίηση πολύ μεγάλων γράφων. Από αυτή τη μελέτη προέκυψε μια καινοτόμα μεθοδολογία η οποία επιτρέπει την αποδοτική οπτική διερεύνηση πολύ μεγάλων γράφων. Η μεθοδολογία που προτείνεται είναι παρόμοια με την μεθοδολογία που έχει υιοθετηθεί για την διερεύνηση γεωγραφικών χαρτών. Επιπλέον, παρουσιάζεται μια νέα τεχνική για την ευρετηρίαση και την αποθήκευση γράφων. Σε αυτό το πλαίσιο, οι αλληλεπιδράσεις του χρήστη μεταφράζονται σε αποδοτικούς χωρικούς τελεστές. Τέλος, προκειμένου να είναι εφικτή η οπτικοποίηση πολύ μεγάλων γράφων, μια προσέγγιση η οποία βασίζεται σε κατάτμηση εισάγεται. Όσον αφορά στο τρίτο μέρος εργασιών, αντικείμενο έρευνας αποτέλεσε η σημασιολογική ανάλυση δεδομένων, όπου μελετήθηκαν τα ακόλουθα προβλήματα. Αρχικά μελετήθηκε το πρόβλημα της ενοποίησης μεταξύ του Σημασιολογικού και του XML περιβάλλοντος. Για το πρόβλημα αυτό, παρουσιάζεται ένα διαλειτουργικό πλαίσιο το οποίο προσφέρει δυνατότητες μετάφρασης ερωτήσεων καθώς και αντιστοίχισης και μετασχηματισμού σχημάτων. Πιο συγκεκριμένα παρουσιάζονται: ένα μοντέλο για την διατύπωση αντιστοιχίσεων μεταξύ OWL-RDF/S και XML Schema, μια μέθοδος για την μετάφραση SPARQL ερωτήσεων σε XQuery, καθώς και ένα μοντέλο για τον μετασχηματισμό XML Schemas σε OWL οντολογίες. Το δεύτερο πρόβλημα αφορά στη χρήση της σημασιολογίας στην επισημείωση και ανάκτηση εγγράφων. Για το πρόβλημα αυτό προτείνεται ένα σημασιολογικό μοντέλο επισημειώσεων, καθώς και μια μέθοδο εκμάθησης για τη σύσταση επισημειώσεων. Τέλος, παρουσιάζεται μια αποτελεσματική μέθοδος ανάκτησης, η οποία εμπλουτίζει τεχνικές ανάκτηση πληροφορίας με σημασιολογία. Στο τελευταίο πρόβλημα, μελετάται η μοντελοποίηση και η εξερεύνηση εξελισσόμενων δεδομένων, υιοθετώντας τεχνικές Διασυνδεμένων Δεδομένων (Linked Data). Αποτέλεσμα αυτής της μελέτης είναι η περιγραφή ενός μοντέλου αλλαγών βασισμένο σε RDF, καθώς και η ανάπτυξη υποδομής Διασυνδεμένων Δεδομένων, η οποία επιτρέπει την διερεύνηση και ανάκτηση εξελισσόμενων δεδομένων.