Συντάχθηκε 24-11-2011 09:06
από Eleni Stamataki
Email συντάκτη: estamataki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: σύνταξη/αποχώρηση υπάλληλος.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Σοφίας Γεωργιακάκη
με θέμα
“Δεικτοδότηση μεγάλης κλίμακας δεδομένων για υποστήριξη χωρικών επερωτημάτων στο Hadoop DFS”
“Indexing large-scale data to support spatial queries on Hadoop DFS”
[Παρασκευή 25 Νοεμβρίου 2011 , ώρα 13.15]
[Αίθουσα 2042, Κτίριο Επιστημών, Πολυτεχνειούπολη]
Εξεταστική Επιτροπή
Επ. Καθηγητής Αντώνιος Δεληγιαννάκης (επιβλέπων)
Καθηγητής Μίνως Γαροφαλάκης
Επ. Καθηγητής Βασίλης Σαμολαδάς
Περίληψη
Ποικίλα συστήματα καλούνται να διαχειριστούν μεγάλο όγκο πολυδιάστατων δεδομένων. Οι δομές δεικτοδότησης R-trees μπορούν να επιταχύνουν ένα φάσμα επερωτημάτων, αποφεύγοντας τη σάρωση όλων των δεδομένων. Δεδομένου του όγκου των δεδομένων και της πολυπλοκότητας των επερωτημάτων, υλοποιήσαμε έναν αλγόριθμο για την κατασκευή μιας ιεραρχικής στατικής δομής δεικτοδότησης τύπου Packed Hilbert R-tree στο κατανεμημένο σύστημα αρχείων Hadoop DFS. Επιπλέον, σχεδιάσαμε και υλοποιήσαμε τρεις διαφορετικές στρατηγικές εκτέλεσης δέσμης τοπολογικών χωρικών επερωτημάτων (Range & Point Queries) στο περιβάλλον Hadoop MapReduce, χρησιμοποιώντας το αποθηκευμένο στο HDFS R-tree. Η πειραματική αξιολόγηση δείχνει την καλή απόδοση του αλγορίθμου κατασκευής R-tree, και την δυνατότητα των μεθόδων εκτέλεσης επερωτημάτων να ανταπεξέλθουν σε δέσμες επερωτημάτων σε διαφορετικές συνθήκες, ανάλογα με τη φύση των επερωτημάτων και το μέγεθος του cluster.
Abstract
Various systems need to handle massive amounts of multidimensional data. R-tree indexing structures can speed up a range of queries, by avoiding a full scan of the data set. Considering the large amount of data and the complexity of the queries, we implemented an algorithm for the construction of a hierarchical static Packed Hilbert R-tree indexing structure on the Hadoop distributed filesystem (HDFS). Moreover, we designed and implemented 3 different strategies for processing a batch of topological spatial queries (Range & Point Queries) using the Hadoop MapReduce framework, exploiting the R-tree that resides on the HDFS. The experimental evaluation shows the good performance of the algorithm that builds the R-tree, and the ability of the 3 query processing methods to handle batches of queries under different circumstances regarding the form of the queries and the size of the cluster.
