Management of historical information and preference in massive datasets

Abstract

A distinctive phenomenon of the past two decades has been the explosive data generation increase that is witnessed through a multitude of sources. Social networks and content provider websites as well as organizations and enterprises in other disciplines such as astronomy and genomics report daily data storage and data processing quantities of demanding volume. It is important, therefore, for solutions that target problems in this modern environment to be largely space efficient while retaining their time efficiency. To this end, this thesis tackles challenges related to preference query evaluation as well as historical information management by proposing algorithms and data structures that are linear in their space cost. More specifically, the first part of the thesis deals with the dynamic maintenance of top-k dominating points and the evaluation of dynamic 3-sided skyline queries in the presence of dataset updates. The second part of the thesis presents a prototype system termed HiNode that maintains graph historical information from evolving graph sequences in an asymptotically space-optimal manner. Finally, two implementations of HiNode with different underlying technologies are described in detail and are extensively evaluated.

H εκρηκτική αύξηση του ρυθμού παραγωγής δεδομένων η οποία παρατηρείται από πλήθος διαφορετικών πηγών, αποτελεί ένα χαρακτηριστικό φαινόμενο των τελευταίων δύο δεκαετιών. Ιστοσελίδες παροχής περιεχομένου, κοινωνικά δίκτυα καθώς επίσης και επιχειρήσεις ή οργανισμοί διαφόρων πεδίων όπως Αστρονομία και Γονιδιωματική έχουν καθημερινές ανάγκες αποθήκευσης και επεξεργασίας δεδομένων οι οποίες απαιτούν ένα σημαντικό πλήθος πόρων. Προκύπτει, επομένως, η ανάγκη εύρεσης λύσεων στα προβλήματα των σύγχρονων εφαρμογών οι οποίες θα χαρακτηρίζονται τόσο από χρονική όσο και από χωρική αποδοτικότητα. Για το σκοπό αυτό, η παρούσα διατριβή μελετάει ζητήματα που σχετίζονται με τον αποδοτικό υπολογισμό ερωτημάτων προτίμησης καθώς και την αποδοτική διαχείριση ιστορικής πληροφορίας προτείνοντας αλγορίθμους και δομές δεδομένων με γραμμικό χωρικό κόστος. Πιο συγκεκριμένα, το πρώτο μέρος της διατριβής ασχολείται με τη δυναμική διατήρηση των k κορυφαίων σημείων κυριαρχίας και τον υπολογισμό 3-πλευρών ερωτημάτων κορυφογραμμής σε πλήρως δυναμικά σύνολα δεδομένων. Το δεύτερο μέρος της διατριβής παρουσιάζει ένα πρότυπο σύστημα με το όνομα HiNode το οποίο διαχειρίζεται ιστορική πληροφορία σε ακολουθίες εξελισσόμενων γραφημάτων και χαρακτηρίζεται από ασυμπτωτικά βέλτιστο χωρικό κόστος. Τέλος, περιγράφονται δύο υλοποιήσεις για το σύστημα HiNode, που βασίζονται σε διαφορετικές υποκείμενες τεχνολογίες, οι οποίες ακολούθως αξιολογούνται πειραματικά.