Συντάχθηκε 13-12-2013 10:10
από Eleni Stamataki
Email συντάκτη: estamataki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: σύνταξη/αποχώρηση υπάλληλος.
Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΣΤΕΛΛΑ ΜΑΡΟΠΑΚΗ
με θέμα
Παράλληλος Υπολογισμός Κορυφογραμμής σε Σύστημα Απεικόνισης-Ελάττωσης
Parallel Skyline Computation on Map-Reduce Systems
Τρίτη 17 Δεκεμβρίου 2013, 10πμ
Αίθουσα 141.Α11 (Αίθουσα Συνεδριάσεων Softnet), Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Επίκουρος Καθηγητής Αντώνιος Δεληγιαννάκης (επιβλέπων)
Καθηγητής Μίνως Γαροφαλάκης (Σχολή ΗΜΜΥ)
Επίκουρος Καθηγητής Βασίλης Σαμολαδάς (Σχολή ΗΜΜΥ)
Περίληψη
Τις τελευταίες δεκαετίες, η διαχείριση και η αποθήκευση των δεδομένων γίνονται όλο και πιο κατανεμημένα. Σύνθετοι τελεστές επερωτήσεων, όπως η επερώτηση κορυφογραμμής, είναι όχι απλώς χρήσιμοι, αλλά απαραίτητοι προκειμένου να βοηθήσουν τους χρήστες να χειριστούν τον τεράστιο όγκο των διαθέσιμων δεδομένων με την αναγνώριση ενός υποσυνόλου από ενδιαφέροντα αντικείμενα. Τεχνικές για τον διαχωρισμό του χώρου των δεδομένων, όπως η αναδρομική κατανομή του χώρου, έχουν χρησιμοποιηθεί για τον υπολογισμό της επερώτησης κορυφογραμμής σε κεντρικοποιημένα, παράλληλα και κατανεμημένα συστήματα. Δυστυχώς τέτοιου είδους διαχωρισμός του χώρου δεδομένων δεν είναι κατάλληλος στην περίπτωση παράλληλων συστημάτων όπου όλα τα χωρίσματα επεξεργάζονται ταυτόχρονα, δεδομένου ότι πολλά από αυτά δεν συμβάλουν στο συνολικό αποτέλεσμα της επερώτησης κορυφογραμμής, με αποτέλεσμα να υπάρχουν πολλοί περιττοί υπολογισμοί.
Η παρούσα διπλωματική εργασία επικεντρώνεται στο σχεδιασμό, την υλοποίηση και την σύγκριση δύο αλγορίθμων για παράλληλο υπολογισμό επερώτησης κορυφογραμμής. Η παρουσιαζόμενη υλοποίησή είναι βασισμένη στο μοντέλο Απεικόνισης - Ελάττωσης και στην ανοιχτού κώδικα υλοποίησή του, το Hadoop. Χρησιμοποιήθηκαν τεχνικές για το διαχωρισμό του χώρου των δεδομένων που έχουν εφαρμοστεί παλαιότερα με τέτοιο τρόπο ώστε να είναι δυνατή η παραλληλοποίησή τους στο σύστημα Απεικόνισης - Ελάττωσης και σε υπολογισμό σε ένα βήμα. Παρατίθεται ένα σύνολο πειραμάτων από τα οποία αποδεικνύεται ότι οι εν λόγω τεχνικές είναι κατάλληλες για παράλληλο υπολογισμό του επερωτήματος κορυφογραμμής. Παρέχεται επίσης μία συγκριτική ανάλυση της απόδοσης των δύο αλγορίθμων που χρησιμοποιούνται. Όπως θα δειχθεί από τις πειραματικές μελέτες, οι εν λόγω τεχνικές είναι αποτελεσματικές και δίνουν μία επεκτάσιμη λύση για τον υπολογισμό της επερώτησης κορυφογραμμής σε παράλληλα περιβάλλοντα.
Abstract
During the last decades, data management and storage have become increasingly distributed. Advanced query operators, such as skyline queries, have become, not just useful, but indispensable, in order to help users handle the huge amount of available data by identifying a set of interesting data objects. Space partition techniques, such as recursive division of the data space, have been used for skyline query processing in centralized, parallel and distributed settings. Unfortunately, such grid-based partitioning is not suitable in the case of a parallel skyline query, where all partitions are examined simultaneously, since many data partitions do not contribute to the overall skyline set, resulting in a lot of redundant processing.
This thesis focuses on studying the design, development and comparison of two algorithms to parallel skyline query computation. The presented implementation is based on the Map-Reduce model and its open-source implementation, Hadoop, using space partitioning techniques that were introduced earlier in a parallelizable way over the Map-Reduce model of computation in one step. A set of experiments will be demonstrated that will show that these techniques are suitable for skyline query processing in parallel architectures. A comparative performance analysis for the two algorithms used, will also be provided. As it will be demonstrated by experimental studies, these techniques are an efficient and scalable solution for skyline query processing in parallel environments.
