Interval data management in main memory
Authors: Χριστοδούλου Γεώργιος 
Published: September 2023

Η διαχείριση των δεδομένων εύρους έχει αποτελέσει έναν ενεργό τομέα έρευνας από όταν εφευρέθηκαν οι βάσεις δεδομένων. Μια δημοφιλής κατεύθυνση έρευνας είναι η ευρετηρίαση και η ανάκτηση διαστημάτων, που βρίσκει ένα μεγάλο πεδίο εφαρμογών. Ένα μεγάλο σύνολο συστημάτων βασίζεται σε χρονικά και δεδομέναμε ανακριβείς τιμές. Πολλοί αλγόριθμοι και ευρετήρια έχουν προταθεί, με στόχο την απάντηση διάφορων τύπων ερωτημάτων. Οι περισσότεροι αλγόριθμοι είναι είτε μη βέλτιστοι ως προς την χρήση χώρου είτε αποδίδουν καλά μόνο για συγκεκριμένουςτύπους ερωτημάτων. Χρειαζόμαστε νέα και αποδοτικά ευρετήρια στην κύρια μνήμηγια δεδομένα εύρους, τα οποία μπορούν να εκτελούν ερωτήματα με υψηλή απόδοση. Σε αυτήν τη διδακτορική διατριβή, στοχεύουμε στην έρευνα μεθόδων ευρετηρίασης,οι οποίες είναι ευέλικτες, έχουν χαμηλές απαιτήσεις χώρου και παρέχουν υψηλή απόδοση στην απάντηση ερωτημάτων. Σε στατιστικές και πιθανοτικές βάσεις δεδομένων [3], δεδομένα με ανακριβείς τιμές συχνά προσεγγίζονται με εύρη (διαστήματα τιμών). Παραδείγματα πραγματικού κόσμου των δεδομένων με ανακριβείς τιμές περιλαμβάνουν μετρήσεις θερμοκρασίας που λαμβάνονται από συσκευές IoT ή καταγραφή χρονοσειρών. Για τέτοιες περιπτώσεις, θα ήταν πιο κατάλληλο να καταγράφεται μια παρατήρηση χρησιμοποιώντας ένα διάστημα τιμών αντί για μια μεμονωμένη τιμή ή μια ακολουθία παρόμοιων τιμών. Στην ανωνυμοποίηση δεδομένων [4], οι τιμές των χαρακτηριστικών των εγγραφών ενός πίνακα μπορούν να γενικευτούν σε εύρη. Οι αποθηκευμένες τιμές μπορούν να αντικατασταθούν με σημασιολογικά συνεπείς, αλλά λιγότερο ακριβείς εναλλακτικές αναπαραστάσεις υπό την μορφή εύρους. Με αυτόν τον τρόπο, πληροφορίες από πίνακες με ευαίσθητα δεδομένα, όπως η ταυτότητα οποιουδήποτε ατόμου στο οποίο αναφέρονται τα δεδομένα, δεν μπορούν να αναγνωριστούν. Στις τεχνικές ευρετηρίασης δεδομένων XML [5], το εύρος ενός στοιχείου XML μπορεί να μοντελοποιηθεί ως ένα εύρος που καθορίζεται από τις θέσεις της αρχικής και της κλείσιμος ετικέτας του στοιχείου. Πολύ συχνά, αυτά τα εύρη αντιπροσωπεύουν χρονικά διαστήματα περιγραμμέναμε την μορφή μιας πλειάδας [α, β]. Σε μια χρονική βάση δεδομένων, ένα μοντέλο δεδομένων που βασίζεται σε εύρη μπορεί να αντιστοιχίσει την τιμή ενός γνωρίσματος με ένα αντίστοιχο χρονικό εύρος ισχύος. Εκτός από τον χρόνο ισχύος, ένα μοντέλο με βάση τα εύρη μπορεί να χαρακτηρίσει χρονικά τον χρόνο συναλλαγής,που απαθανατίζει τις στιγμές που μια πλειάδα εισάγεται και διαγράφεται από τη βάση δεδομένων. Τα διαστήματα δεικτοδοτούνται από δομές δεδομένων για να αξιολογηθούν αποδοτικά διάφοροι τύποι ερωτημάτων. Υπάρχουν αρκετοί τύποι ερωτημάτων πάνω σε διαστήματα, με τη διάκριση τους να βρίσκεται στους περιορισμούς που διαμορφώνουν το σύνολο των διαστημάτων που προκύπτει ως επιθυμητό αποτέλεσμα, ή στο πλαίσιο με το οποίο μοντελοποιούμε τα δεδομένα μας. Το θέμα αυτής της διατριβής είναι να μελετήσουμε το πρόβλημα της ευρετηρίασης και της αναζήτησης σε μια μεγάλη συλλογή δεδομένων, βασισμένη σε ένα εύρος που χαρακτηρίζει κάθε αντικείμενο. Η συλλογή μπορεί να είναι γνωστή πριν τη δημιουργία του ευρετηρίου ή να εξελιχθεί με τον χρόνο, κάτι το οποίο συνηθίζεται σε χρονικές βάσεις δεδομένων ή ροές δεδομένων. Η πρόκληση είναι να βρούμε λύσεις που μπορούν να εκμεταλλευτούν το σύγχρονο υλικό, όπως μεγάλες κύριες μνήμες, οι οποίες να μπορούν να χειριστούν την παραδοσιακή και την ευέλικτη ευρετηρίαση των ευρών και να παρέχουν υψηλή απόδοση για μια ευρεία ποικιλία τύπων ερωτημάτων. Σε αυτήν τη διατριβή, μελετούμε πολλά προβλήματα και διαφορετικά σενάρια που συνδέονται με την ευρετηρίαση και την αναζήτηση δεδομένων διαστημάτων. Στο πρώτο μέρος, ασχολούμαστε με τη διαχείριση μη μεταβαλλόμενων (καλώς καθορισμένων) διαστημάτων τιμών, και προτείνουμε το HINT, ένα νέο και αποδοτικό ευρετήριο στην κύρια μνήμη, με εστίαση σε ερωτήματα εύρους, τα οποία αποτελούν βασικό στόχο της έρευνας. Το HINT εφαρμόζει μια ιεραρχική προσέγγιση ευρετηρίασης, που αναθέτει κάθε διάστημα σε το πολύ δύο διαμερίσματα ανά επίπεδο και έχει ελεγχόμενες απαιτήσεις χώρου. Μειώνουμε την πληροφορία που αποθηκεύουμε για τα δεδομένα στο ελάχιστο, χωρίζοντας τα δεδομένα σε ομάδες βάσει του αν η αρχή τους βρίσκεται εντός ή εκτός από τα όρια ενός διαμερίσματος. Επι-πλέον, το ευρετήριο μας περιλαμβάνει τεχνικές βελτιστοποίησης αποθήκευσης για την αποτελεσματική διαχείριση αραιών και ασύμμετρα κατανεμημένων στον χώρο δεδομένων. Το δεύτερο πρόβλημα που μελετούμε είναι μια γενικευμένη έκδοση του HINT, έτσι ώστε με την κατάλληλη ρύθμιση αποθήκευσης πληροφοριών, να μπορεί να χειριστεί ερωτήματα με διαφορετικούς περιορισμούς. Τα εύρη μπορεί να ικανοποιούν πιο εξεζητημένες σχέσεις, οι οποίες περιγράφονται στην βιβλιογραφία ως Άλγεβρατου Allen [6] (π.χ. εύρεση όλων των εγγραφών που επικαλύπτονται από το εύροςτου ερωτήματος). Οι αρχές του HINT είναι χρήσιμες για την ανάκτηση δεδομένων εύρους βάσει των σχέσεων του Allen, καθώς η ιεραρχική διαίρεση εφαρμόζεται ανεξάρτητα από τον τύπο του ερωτήματος. Στο τρίτο (και τελευταίο) μέρος αυτής της διατριβής, μελετούμε το πρόβλημα της ευρετηρίασης δεδομένων στο πλαίσιο χρόνου συναλλαγών, δηλαδή την ευρετηρίαση δεδομένων με πολλαπλές εκδόσεις σε μια συνεχώς εξελισσόμενη βάση δεδομένων. Δεδομένου ότι οι κύριες μνήμες των σύγχρονων υπολογιστών είναι μεγάλες και φθηνές, μπορούμε να επιτρέψουμε την αποθήκευση όλων των εκδόσεων ενός εξε-λισσόμενου πίνακα στη μνήμη. Αυτό θέτει το εξής ερώτημα: πώς δημιουργήσουμε αποτελεσματικά ένα ευρετήριο για έναν τέτοιο πίνακα; Σε αντίθεση με την κλασική προσέγγιση ευρετηρίασης, όπου τόσο οι τρέχουσες (δηλαδή ενεργές) όσο και οι παλιές (δηλαδή ανενεργές) εκδόσεις δεδομένων συνυπάρχουν στην ίδια δομή δεδομένων, προτείνουμε το LIT, ένα υβριδικό ευρετήριο, που ξεχωρίζει τη διαχείριση των ενεργών και ανενεργών καταστάσεων των δεδομένων. Το LIT περιλαμβάνει τεχνικές βελτιστοποίησης για την αποδοτική ευρετηρίαση, και υποστηρίζει αποτελεσματικά ερωτήματα αλλά και ενημερώσεις στις εκδόσεις των δεδομένων. Για την συνολική αξιολόγηση όλων των μεθόδων μας, χρησιμοποιήσαμε πολλά πραγματικά και συνθετικά σύνολα δεδομένων με ποικίλα χαρακτηριστικά, ώστε να μπορούμε να συμπεράνουμε με ασφάλεια την αξιοπιστία των αλγορίθμων μας. Τα πειράματα δείχνουν πως οι αλγόριθμοί μας είναι, στην γενική περίπτωση, μια τάξη μεγέθους πιο γρήγοροι από τις υπάρχουσες μεθόδους σε συλλογές στατικών ή εξελισσόμενων δεδομένων και με διαφορετικούς τύπους ερωτημάτων.