Θεμελιώδεις αρχές αναλυτικής επεξεργασίας πληροφοριών

Abstract

A common operation involved with the majority of algorithms relevant to On-Line Analytical Processing is aggregation, which can be extremely time-consuming if applied over large datasets. To overcome this drawback, scientists have proposed the precomputation and materialization of a large volume of aggregated data into a structure called data cube. Nevertheless, the construction and usage of the data cube itself has been found very demanding in terms of computational and storage resources. In this dissertation, we study this problem in depth and propose comprehensive suites of scalable algorithms that perform efficient cube construction, storage, query answering, incremental updating, indexing, and caching. Our extensive experimental evaluation indicates that our solutions are viable even when applied over very large datasets with arbitrary hierarchies. Some key points in our work include the introduction of a novel storage scheme for cubes that is based on the use of row-id references, a new external partitioning algorithm, an efficient construction plan, and the use of on- demand approaches for processes that are too expensive to perform in a given window of time. A unique property of all our algorithms is their compatibility with the relational model, which makes them easy to incorporate into existing relational servers. Finally, as an application in data mining, we study the usage of aggregate queries for solving the problems of feature selection and classification and propose a disk-based, lazy, and accurate solution, which exhibits great potentials in a broad range of applications.

Μία κοινή λειτουργία που χρησιμοποιείται από την πλειοψηφία των αλγορίθμων που σχετίζονται με το χώρο της Άμεσης Αναλυτικής Επεξεργασίας είναι η συνάθροιση δεδομένων, μία διαδικασία εξαιρετικά χρονοβόρα όταν εκτελείται πάνω από πολύ μεγάλα σύνολα δεδομένων. Για την αντιμετώπιση του προβλήματος αυτού, έχει προταθεί ο προ-υπολογισμός και η αποθήκευση ενός μεγάλου όγκου συναθροισμένων δεδομένων σε μία δομή που ονομάζεται κύβος δεδομένων. Ωστόσο, η κατασκευή και η χρήση του ίδιου του κύβου δεδομένων έχουν βρεθεί πολύ απαιτητικές όσον αφορά την κατανάλωση υπολογιστικών και αποθηκευτικών πόρων. Στην παρούσα διατριβή, μελετούμε το ανωτέρω πρόβλημα σε βάθος και προτείνουμε ολοκληρωμένες ομάδες αλγορίθμων που προσφέρουν στον κύβο αποδοτική κατασκευή, αποθήκευση, απάντηση επερωτήσεων, βαθμιαία ενημέρωση, ευρετηρίαση, και δυνατότητες χρήσης ενδιάμεσης μνήμης. Η εκτενής πειραματική μας αξιολόγηση υποδεικνύει ότι οι λύσεις μας είναι βιώσιμες ακόμα και όταν εφαρμόζονται πάνω από πολύ μεγάλα σύνολα δεδομένων με απεριόριστες ιεραρχίες. Κάποια σημαντικά σημεία στην εργασία μας είναι η εισαγωγή ενός καινοτόμου σχήματος αποθήκευσης κύβων που βασίζεται στη χρήση αναφορών αναγνωριστικού γραμμής, ένας νέος αλγόριθμος εξωτερικού διαμερισμού, ένα αποδοτικό πλάνο δημιουργίας, και η χρήση προσεγγίσεων κατ' ανάγκη για διαδικασίες που είναι πολύ ακριβές για να ολοκληρωθούν στα όρια ενός δεδομένου χρονικού παραθύρου. Μία μοναδική ιδιότητα όλων των αλγορίθμων μας αποτελεί η συμβατότητά τους με το σχεσιακό μοντέλο, γεγονός που καθιστά την ενσωμάτωσή τους σε οποιονδήποτε υπάρχοντα σχεσιακό εξυπηρετητή σχετικά απλή. Τέλος, σαν μία εφαρμογή των ιδεών μας στην εξόρυξη δεδομένων, μελετούμε τη χρήση συναθροιστικών επερωτήσεων για την επίλυση των προβλημάτων επιλογής χαρακτηριστικών και ταξινόμησης, και προτείνουμε μία τεμπέλικη λύση ικανοποιητικής ακρίβειας, που είναι ικανή να επεξεργάζεται δεδομένα στο δίσκο και επιδεικνύει μεγάλες δυνατότητες σε ένα ευρύ φάσμα εφαρμογών.