Interval data management in main memory

Abstract

The management of intervals has been an active research area since databases were invented. A popular direction of research is the indexing and retrieval of intervals, finding a wide range of applications. Emerging and widely used systems are built dependent on temporal and uncertain data. Many algorithms and indices have been proposed, concentrated on a variety of queries. Most algorithms are either suboptimal in space consumption or perform well only for specific query types. We need novel and efficient in-memory indices for intervals, which can evaluate queries with high performance. In statistical and probabilistic databases [3], uncertain values are often approximated by confidence intervals. Real-world examples of uncertain values include temperature values obtained from IoT devices or time-series. For such cases, it would be more appropriate to record an observation using an interval range rather than a single value. In data anonymization [4] attributes can be generalized to intervals. Stored values can be replaced with semantically consistent but less precise alternatives in the form of intervals. In this way, information from a private table, like the identity of any individual to whom the released data refer cannot be recognized. In XML data indexing techniques [5], the scope of an XML element can be modeled as an interval defined by the positions of the starting and closing tag of the element. Intervals are representations of value ranges. Quite often, these ranges represent periods of time described as a tuple [start, end]. In a temporal database, an interval based data model can timestamp each tuple or attribute value with a validity time interval. Along with valid time, an interval-based model can timestamp transaction time, which captures when a tuple is inserted and deleted from the database. We index intervals in data structures so that we can efficiently evaluate different types of queries. There are several query types over intervals, with the differentiation lying on the specifications that shape the resulting set of intervals, or the context in which we model data with an interval representation. The topic of this dissertation is to study the problem of indexing and querying a large collection of records, based on an interval attribute that characterizes each object. We focus on the different aspects of temporal databases, as they form the most significant application of interval data. The collection can be known before indexing or evolve over time, which is common in temporal databases or streaming data. The challenge is to find solutions which, can take advantage of modern hardware such as large main memories, can handle traditional and on demand indexing of intervals, and provide high performance for a wide variety of query types and predicates. In this thesis, we study numerous problems and different scenarios which come down to indexing and querying interval data. In the first part, we propose HINT, a novel and efficient in-memory index for large known collections of intervals, with a focus on range queries, which are a basic component of many search and analysis tasks. Our index is suitable for valid-time indexing in the context of temporal databases. HINT applies a hierarchical partitioning approach, which assigns each interval to at most two partitions per level and has controlled space requirements. We reduce the information stored at each partition to the absolutely necessary by dividing the intervals in groups, based on whether they begin inside or before the partition boundaries. In addition, our index includes storage optimization techniques for the effective handling of data sparsity and skewness. The second problem we study, is a more general version of HINT, so that with the best trade-off in information storage, it will be able to handle queries with different predicates. Intervals may satisfy more sophisticated relations than intersections, which are based on Allen’s relationships [6] (e.g., find all intervals that are covered by the query interval). The principles of HINT are useful for the retrieval of data intervals based on Allen’s relationships, because the hierarchical partitioning applies independently of the query type. We show how HINT can be tuned depending on the data and can be efficiently used to process joins and queries based on Allen’s relationships. In the last part of this dissertation, we study the problem of transaction-time indexing in the context of temporal databases, i.e., indexing versions of data in an evolving database. Given the fact that the main memories of modern commodity are large and cheap, we can afford to keep track of all versions of an evolving table in memory. This raises the question of how to index such a table effectively. We depart from the classic indexing approach, where both current (i.e., live) and past(i.e., dead) data versions are indexed in the same data structure, and propose LIT, a hybrid index, which decouples the management of the current and past states of the indexed column. LIT includes optimized indexing modules for dead and live records, which support efficient queries and updates, and gracefully combines them. For the evaluation of our methods, we used multiple real and synthetic datasets with different characteristics so that we can safely conclude the robustness of our algorithms. The experiments showed that our algorithms are typically one order of magnitude faster than existing methods on static or evolving data collections and with multiple types of queries.

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