Αποδοτικές μέθοδοι προσπέλασης πολυδιάστατων δεδομένων μερικών χώρων

Abstract

Η αποθήκευση και η ανάκτηση πληροφοριών αποτελούν δύο από τις πλέον θεμελιώδεις λειτουργίες των υπολογιστών. Παρά το ότι προηγηθείσες μελέτες έχουν αποδώσει έναν σημαντικό αριθμό αποδοτικών μεθόδων προσπέλασης, το πεδίο έρευνας στον νευραλγικό αυτό χώρο παραμένει ανοικτό. Το ανωτέρω γεγονός οφείλεται τόσο στον συνεχώς αυξανόμενο όγκο πληροφοριών ο οποίος συνδέεται με μεγάλο πλήθος σύγχρονων εφαρμογών που επιτάσσει την αποδοτική διαχείριση του, όσο και στην πολυπλοκότητα του πεδίου ορισμού των δεδομένωνκαι των χειρισμών που πρόκειται να εκτελεστούν σε αυτά. Η έντονη ανταπόκριση της ερευνητικής κοινότητας επιφέρει την παροχή ενός αμείωτου αριθμού παρουσιάσεων νέων μεθόδων προσπέλασης και βελτίωσης υπαρχουσών. Ο κορμός της παρούσας διατριβής αποτελείται από τέσσερα κεφάλαια. Στα τρία από αυτά παρουσιάζονται ισάριθμες μέθοδοι προσπέλασης πολυδιάστατων δεδομένων οι οποίες κάνουν χρήση των ιδιοτήτων των μετρικών χώρων. Στο τέταρτο προτείνεται ένας διαχειριστής αποθήκευσης μόνιμης γνώσης. Η πρώτη από τις μεθόδους προσπέλασης, το Gr-δέντρο, συνδυάζει επιτυχώς τις δυνατότητες που παρέχουν οι συναρτήσεις απόστασης των μετρικών χώρων με τα χαρακτηριστικά των G-δέντρων. Η ειδοποιός διαφορά του Gr-δέντρου από το G-δέντρου είναι η ενεργή περιοχή χωρίσματος, η οποία αποτελεί έναν περιορισμό στο χώρο που καταλαμβάνουν τα δεδομένα μέσα στο χώρισμα. Η προτεινόμενη δομή αποτελείται από τρία στρώματα. Το εσωτερικό στρώμα, το στρώμα-φύλλο και το στρώμα των ενεργών περιοχών. Το τελευταίο παρεμβάλλεται μεταξύ του στρώματος-φύλλου και τωνδεδομένων με αποτέλεσμα την ελάττωση των απαιτούμενων προσπελάσεων για την απάντηση των επερωτήσεων ορίων και των μερικώς ταιριασμένων επερωτήσεων. Το πλεονέκτημα του Gr-δέντρου έναντι του G-δέντρου ισχυροποιείται όταν τα δεδομένα δεν είναι ομοιόμορφα κατανεμημένα μέσα στο χώρισμα τους και όταν αυξάνονται οι διαστάσεις και ο αριθμός των εγγραφών. Επιπλέον, το Gr-δέντρο ελαττώνει το κόστος της αναζήτησης του πραγματικού χωρίσματος της εγγραφής μετά από την εύρεση του αρχικού χωρίσματος της. Για την αποφυγή μεγάλου κόστους αποθήκευσης και περιττών προσπελάσεων, το Gr-δέντρο αποθηκεύει τις ενεργές περιοχές των χωρισμάτων μόνο εάν η επικάλυψη τους με το χώρισμα είναι μικρότερη από ένα ποσοστό που ορίζεται παραμετρικά. Επιπροσθέτως, για να πραγματοποιηθεί προσπέλαση σε κόμβο ενεργών περιοχών θα πρέπει τα χωρίσματα που συνδέονται με αυτόν και που πιθανόν να περιέχουν απαντήσεις, να υπερβαίνουν έναν αριθμό που επίσης ορίζεται παραμετρικά. Το Gr-δέντρο προβαίνει σε επιπλέον μείωση των προσπελάσεων για στατικά ή σχεδόν στατικά δεδομένα με την χρησιμοποίηση της πολιτικής των περαιτέρω διασπάσεων. Η πολιτική αυτή αποσκοπεί στην δημιουργία όσο το δυνατόν μικρότερου μεγέθους χωρισμάτων. Η δεύτερη μέθοδος προσπέλασης που παρουσιάζουμε, το ΜΒ-δέντρο, χρησιμοποιεί ένα καινούργιο σχήμα διαχωρισμού που στηρίζεται σε ομόκεντρες σφαίρες. Με βάση αυτό οργανώνει πολυδιάστατους χώρους δεδομένων σε μη κενά και μη επικαλυπτόμενα χωρίσματα κάνοντας χρήση των δυνατοτήτων που παρέχουν οι συναρτήσεις απόστασης των μετρικών χώρων και τα Β-δέντρα. Το MB-δέντρο απαιτεί μικρό αποθηκευτικό χώρο λόγω του ότι για κάθε χώρισμα φυλάσσεται μόνο ένας πραγματικός αριθμός. Επιπλέον, δεν επηρεάζεται από την κατανομή που ακολουθούν τα δεδομένα. Είναι αποδοτικό για τις ακριβώς ταιριασμένες επερωτήσεις και διαχειρίζεται καλά τις επερωτήσεις ομοιότητας, ενώαπαιτεί πολύ μικρούς χρόνους για όλες τις ενέργειες που σχετίζονται με την δυναμική του. Η τρίτη μέθοδος προσπέλασης που εισάγουμε, το Τοξοειδές δέντρο, στηρίζεται στην Τοξοειδή καμπύλη. Αυτή είναι μία νέα καμπύλη που καλύπτει τον χώρο η οποία, σε αντίθεση με τις υπόλοιπες, δεν χρησιμοποιεί πλέγμα για τον διαχωρισμό του χώρου των δεδομένων. Το Τοξοειδές δέντρο οργανώνει τον χώρο σε μη επικαλυπτόμενα τοξοειδή χωρίσματα διαμέσου διασπάσεων που επιβάλλονται από τεμνόμενα επίπεδα και ομόκεντρες σφαίρες τα οποία εναλλάσσονται με συγκεκριμένη σειρά. Το Τοξοειδές δέντρο χρησιμοποιεί την εναλλαγή μπιτ, συνδυάζει τα χαρακτηριστικά των μετρικών χώρων και των Β-δέντρων και επεκτείνει το MB-δέντρο. Αποκλείει την αποθήκευση κενών χωρισμάτων και είναι ανεξάρτητο της κατανομής των δεδομένων. Το Τοξοειδές δέντρο παρουσιάζει όπως και το MB-δέντρο συμμετρία, καθόσον τακτοποιεί τα χωρίσματα γύρω από ένα σημείο εκκίνησης. Το γεγονός αυτό καθιστά την μέθοδο ιδιαίτερα κατάλληλη για εφαρμογές, στις οποίες εξετάζονται επερωτήσεις απόστασης και αναζητήσεις σε επίπεδα που περνούν από το σημείο εκκίνησης καθώς και κώνους που έχουν το σημείο αυτό για κορυφή τους. Το σύνολο των υποψηφίων να περιέχουν απαντήσεις χωρισμάτων περιορίζεται με την χρήση μασκών από σειρές μπιτ, που εκμεταλλεύονται τον τρόπο με τον οποίον έχουν πραγματοποιηθεί οι διασπάσεις από τα επίπεδα και τις σφαίρες. Και οι τρεις μέθοδοι προσπέλασης που παρουσιάζουμε ενσωματώνουν μια δομή του τύπου Β+-δέντρο για την αποθήκευση των αριθμών διαχωρισμάτων. Αυτό έχει σαν αποτέλεσμα την μείωση του κόστους αναζήτησης που απαιτείται για να βρεθούν όλες οι απαντήσεις μετά από το πρώτο ταίριασμα στο επίπεδο-φύλλο, εφόσον βέβαια απαιτείται να γίνει μία τέτοια κίνηση. Παρά την σταθερή αύξηση της ταχύτητας των υπολογιστών και την ταυτόχρονη μείωση της τιμής της μνήμη τους, η ανάγκη για διαχειριστές αποθήκευσης με έργο την αποδοτική αντιμετώπιση εφαρμογών που να μην είναι δυνατόν να παραμείνουν αποκλειστικά στην κύρια μνήμη, παραμένει ζωτική για τα συστήματα επαγωγικών βάσεων δεδομένων. Κατά συνέπεια, όταν ασχολούμεθα με μεγάλους όγκους προτάσεων, η χρήση της μόνιμης γνώσης είναι αναπόφευκτη, και η χρήση μεθόδων ευρετηριοποίησης ουσιώδης για την αποδοτική απάντηση των επερωτήσεων. Ο προτεινόμενος διαχειριστής αποθήκευσης, PerKMan, χρησιμοποιεί τα G-δέντρα για τη διαχείριση μεγάλου όγκου μόνιμης γνώσης της Prolog. Ο διαχειριστής αυτός μπορεί να συνδεθεί με συστήματα Prolog που παρέχουν μία εξωτερική διεπαφή της γλώσσας προγραμματισμού C. Ο PerKMan διαχειρίζεται με έναν νέο τρόπο ομοιόμορφα γεγονότα και κανόνες, και επιτρέπει διαφορετικά γνωρίσματα ενός κατηγορήματος να αποθηκεύονται στην ίδια διάσταση, εφόσον είναι του ιδίου τύπου. Ο σχεδιασμός του επιτρέπει την διαχείριση των κατηγορημάτων με συνολοστρεφείς και προτασοστρεφείς πράξεις. Οι δομές δεδομένων του προσαρμόζουν το σχήμα τους ανεξάρτητα από την κατανομή των δεδομένων. Ο PerKMan υποστηρίζει την χρήση σύνθετων όρων με την ισοπέδωση και την εισαγωγή τους στο ευρετήριο και είναι κατάλληλος για την αποτελεσματική διαχείριση μεγάλων βάσεων γνώσης. Για τις μεθόδους προσπέλασης και τον διαχειριστή αποθήκευσης παρουσιάζονται αλγόριθμοι εισαγωγής και διαγραφής δεδομένων, αναφέρεται ο τρόπος με τον οποίον πραγματοποιούνται οι αναζητήσεις για διάφορους τύπους επερωτήσεων, παρέχονται μαθηματικές εκφράσεις, σχολιάζονται σημεία που άπτονται των υλοποιήσεων, αναφέρονται πειραματικά αποτελέσματα και συγκρίσεις με συναφείς εργασίες. Επιπλέον, δίνονται μελλοντικές κατευθύνσεις για επόμενα ερευνητικά βήματα. Θεωρούμε ότι τόσο το Gr-δέντρο όσο και το MB-δέντρο και το Τοξοειδές δέντρο δικαιολογούν το κίνητρο σχεδιασμού τους που είναι η αποδοτική διαχείριση μεγάλου όγκου πολυδιάστατων δεδομένων για διάφορους τύπους επερωτήσεων, επεκτείνουν αποτελεσματικά το σύνολο των μεθόδων προσπέλασης και αποτελούνυποσχόμενες επιλογές για χρήση από εφαρμογές βάσεων δεδομένων και βάσεων γνώσης. Επιπλέον, ο PerKMan ελαττώνει τις προσπελάσεις στο δίσκο και επιτυγχάνει καλή πληρότητα του διαθέσιμου χώρου, χωρίς το επιπλέον κόστος που θα επέφερε μία δευτερεύουσα ευρετηριοποίηση.