Ευρετηριοποίηση χωροχρονικών δεδομένων με το hBΠ-tree

Abstract

Οι εφαρμογές των βάσεων δεδομένων γίνονται ολοένα πιο πολύπλοκες. Τα δεδομένα που αποθηκεύονται στην πλειονότητα αυτών είναι δεδομένα που απαιτούν ταυτόχρονη ευρετηριοποίηση με βάση περισσότερα από ένα χαρακτηριστικά. Παράλληλα, σε πολλές εφαρμογές υπάρχει η ανάγκη να διατηρούνται δεδομένα που αναφέρονται τόσο στο παρόν όσο και στο παρελθόν. Με άλλα λόγια, υπάρχει η ανάγκη καταχώρισης ακόμη μιας διάστασης, της διάστασης του χρόνου. Για την αποδοτική χρήση μιας τέτοιας βάσης χρονικών δεδομένων απαιτείται και η κατάλληλη δομή ευρετηριοποίησης. Στην παρούσα εργασία παρουσιάζουμε τις τροποποιήσεις που πρέπει να γίνουν σε μια δομή ευρετηριοποίησης πολυδιάστατων δεδομένων, το hBπ-tree, ώστε αυτή να υποστηρίζει και χρονικά δεδομένα. Προτείνουμε κάποιες τροποποιήσεις στη δομή του δένδρου και στον αλγόριθμο διάσπασης των κόμβων ώστε το hBπ-tree να αποκτήσει τα χαρακτηριστικά του TSB-tree και να γίνει κατάλληλο για την ευρετηριοποίηση χρονικών ή χωροχρονικών δεδομένων.

Database applications become more and more complex and the data they operate on often has to be indexed using more than one attribute. In addition, there exist and continuously emerge new applications that require a DBMS to manipulate both current and historical data. In other words, there is a pressing demand for indexing data using the time dimension. To efficiently use a temporal database one needs specialized indexing structures. In this paper, we present the modifications that need to be performed on a multi-dimensional index method, the hBπ-tree, so that it becomes appropriate for indexing temporal data. We propose certain modifications on the structure of the index and on the node splitting algorithm that lend the hBπ-tree the characteristics of the TSB-tree and make it suitable for indexing temporal or spatio-temporal data.