Efficient processing of Top-k joins in MapReduce / Hadoop

Abstract

Οι επερωτήσεις σύζευξης με κατάταξη χρησιμοποιούνται ευρέως στην ανάλυση δεδομένων. Ένα από τα πιο γνωστά μοντέλα ανάλυσης δεδομένων είναι το MapReduce και ειδικότερα η ανοιχτού λογισμικού υλοποίησή του, το Apache Hadoop. Εντούτοις, εξαιτίας συγκεκριμένων περιορισμών του μοντέλου, η επεξεργασία των επερωτήσεων σύζευξης με κατάξη στο Hadoop MapReduce, κρίνεται μη αποδοτική για μεγάλους όγκους δεδομένων. Συγκεκριμένα, το μοντέλο MapReduce επεξεργάζεται το σύνολο των δεδομένων που λαμβάνει ως είσοδο, ακόμα και αν είναι εφικτό να γίνει ο υπολογισμός των k καλύτερων αποτελεσμάτων με μέρος μόνο των δεδομένων εισόδου. Επιπροσθέτως, το μοντέλο MapReduce δεν παρέχει τεχνική κατανομής φόρτου για τη δίκαιη κατανομή του φόρτου στους reducers. Αυτές οι δύο αδυναμίες καθιστούν την επεξεργασία των επερωτημάτων σύξευξης με κατάταξη στο MapReduce προβληματική. Στην παρούσα εργασία, προτείνονται τρεις αλγόριθμοι για την αντιμετώπιση των προβλημάτων του έγκαιρου τερματισμού και της κατανομής φόρτου. Οι τεχνικές που προτείνονται, βασίζονται σε αλγόριθμους που χρησιμοποιούν συνόψεις δεδομένων όπως τα ιστογράμματα. Η πειραματική αποτίμηση αποδεικνύει την αποδοτικότητα των προτεινόμενων αλγορίθμων από άποψη χρόνου και εκμεταλλευόμενων πόρων, για ένα πλήθος παραγόντων όπως η τιμή του k, το μέγεθος των αρχείων δεδομένων, την επιλεξιμότητα των δεδομένων και το είδος κατανομής των δεδομένων.