Skyline query processing in Spatial Hadoop

Abstract

Το MapReduce είναι ένα προγραμματιστικό μοντέλο που επιτρέπει την επεξεργασία μεγάλου όγκου δεδομένων σε ένα cluster από μηχανήματα. Ένα MapReduce job διαμοιράζει τα δεδομένα εισόδου σε ένα σύνολο από ανεξάρτητα κομμάτια τα οποία επεξεργάζονται από τις map διεργασίες παράλληλα. Το framework ταξινομεί τις εξόδους των map οι οποίες θα είναι στη συνέχεια είσοδοι στις reduce διεργασίες. Οι είσοδοι και έξοδοι ενός job αποθηκεύονται σε ένα σύστημα αρχείων. Το framework φροντίζει για τον προγραμματισμό και έλεγχο των διεργασιών καθώς και την επανεκτέλεση αποτυχημένων διεργασιών. Το πιο γνωστό ανοιχτού κώδικα λογισμικό είναι το Apache Hadoop. Πρόσφατα, έχει αναπτυχθεί μια επέκταση του Apache Hadoop με ονομασία SpatialHadoop. Το SpatialHadoop έχει σχεδιαστεί ειδικά να χειρίζεται μεγάλα σύνολα χωρικών δεδομένων. Το SpatialHadoop περιέχει έτοιμους χωρικούς τύπους δεδομένων αλλά μας επιτρέπει τη δημιουργία και δικών μας τύπων δεδομένων. Επιπλέον, υποστηρίζει ένα σύνολο από χωρικές λειτουργίες και δείκτες. Σε αυτήν την εργασία, αναπτύξαμε δύο αποδοτικούς αλγόριθμους επεξεργασίας skyline ερωτημάτων και τους υλοποιήσαμε στο SpatialHadoop. Επίσης, τους συγκρίναμε με έναν αλγόριθμο που προτείνεται από το «CG_Hadoop: Computational Geometry in MapReduce» paper. Το αντικείμενο αυτής της μελέτης είναι η υλοποίηση αλγορίθμων που θα είναι αποδοτικοί σε διαφορετικές κατανομές των δεδομένων όπως uniform correlated και anti-correlated. Οι αλγόριθμοι θα πρέπει να δουλεύουν σωστά ανεξάρτητα αν τα αρχεία που επεξεργαζόμαστε περιέχουν ή όχι δείκτες. Για να αξιολογήσουμε την απόδοση των τριών αλγορίθμων υλοποιήσαμε μια σειρά πειραμάτων σε ένα cluster με 17 μηχανήματα.