Adaptive indexing for interactive visual exploration and analytics

Abstract

This thesis introduces novel indexing techniques aimed at facilitating the visual exploration of data stored in large raw files. In today's data-driven society, data is produced at an extraordinary pace, and the ability to rapidly process and comprehend this data is becoming increasingly vital. Conventional data exploration tools heavily rely on Database Management Systems (DBMS), which require data loading and indexing for analysis. However, these procedures can be expensive, time-consuming, and impractical, especially when the data may be discarded after analysis. The initial part of this thesis sheds light on the shortcomings of existing tools and methodologies for in-situ data exploration, establishing a compelling argument for a more efficient system. Subsequently, we present a formal visual exploration model where user operations are translated into data access operations. Furthermore, we unveil novel memory indexing techniques and cost models, with a special emphasis on adaptive indexing and lightweight data structures. These techniques are specifically designed to manage large volumes of raw data, effectively minimizing the I/O cost of accessing the data file and quickly initiating user exploratory analysis by generating a crude version of the index when the user first requests to analyze a file. This index becomes more detailed and adapts to user exploration with each user operation. Additionally, to handle scenarios with limited resources, a resource-aware index initialization mechanism is introduced, and efficient approximation algorithms are proposed to solve the corresponding optimization problem. Through extensive experimentation using both real and synthetic datasets, the proposed techniques have been demonstrated to outperform existing solutions, thus addressing the need for more efficient and intuitive raw data exploration methods. These indexing techniques and schemes form the backbone of the RawVis system, enabling efficient query processing and bypassing expensive data preprocessing steps such as data loading and DBMS indexing. RawVis provides a complete and efficient client-server architecture for visual data exploration directly over the raw data files, including a rich user interface that presents a wide array of options for visualization and analysis. The application of RawVis is demonstrated through a user study, highlighting its ability to offer immediate and meaningful analytics. In summary, this thesis offers a significant contribution to the field of raw data exploration by unveiling a novel system and techniques that notably enhance data handling efficiency, reduce resource usage, and amplify the user experience in terms of speed and interactivity.

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