Diversifying big data in parallel
Φόρτωση...
Ημερομηνία
Συγγραφείς
Νούλης, Κωνσταντίνος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
A characteristic that makes a query result distinctive is apparently quality. One way of
enhancing the quality of a query result is diversification. Many ways have been already
proposed in order to diversify a query result. In this study we utilize the algorithm of
Dissimilarity and Coverage as well as the Max Cover algorithm in an attempt to diversify a
query result, which is substituted by several sets of data. The novelty that is introduced in this
study is the perspective through which we approach those algorithms. Diversification is
conducted with the use of parallel implementations of the aforementioned algorithms in a
distributed environment. With this thesis, we intend to propose a new way of diversifying Big
Data efficiently, taking at the same time advantage of new distributed platforms.
Μια αναζήτηση ενός χρήστη σε μια βάση δεδομένων κρίνεται από το αν και κατά πόσο το αποτέλεσμα αυτής της αναζήτησης θα βοηθήσει το χρήστη να βρει γρήγορα και εύκολα αυτό που ψάχνει. Η ποικιλομορφία των αποτελεσμάτων που παρουσιάζονται μετά από μια αναζήτηση σε μια βάση δεδομένων είναι κάτι που έχει αυξανόμενο επιστημονικό ενδιαφέρον τελευταία. Για να γίνει λοιπόν πιο ποιοτικό και ελκυστικό ένα αποτέλεσμα αναζήτησης επιδέχεται κάποιας επεξεργασίας, πριν την τελική παρουσίαση του στο χρήστη. Η επεξεργασία αυτή καθιστά το αποτέλεσμα της αναζήτησης πιο αξιόπιστο, αφού παρουσιάζει ένα υποσύνολο του αρχικού αποτελέσματος, το οποίο παραθέτει αντιπροσωπευτικά δείγματα και είναι επίσης τόσο διαφοροποιημένο, ώστε τα αποτελέσματα που θα εμφανιστούν στο χρήστη να είναι ποικιλόμορφα και εύστοχα. Μέχρι στιγμής έχουν γίνει διάφορες απόπειρες για τη σχεδίαση ενός μοντέλου που θα παράγει αποτελέσματα με τις παραπάνω ιδιότητες. Κάθε απόπειρα θέτει ένα διαφορετικό ορισμό για τη ποικιλομορφία των δεδομένων, κοιτάζοντας το πρόβλημα από διαφορετική οπτική γωνία. Σε αυτή την εργασία μελετάται ο αλγόριθμος [8] του DisC Diversity. Ανάμεσα στις διάφορες θεωρήσεις, επιλέξαμε να μελετήσουμε τον αλγόριθμο DisC διότι καλύπτει καλύτερα τις ανάγκες του προβλήματος που έχουμε θέσει, επιστρέφοντας στο χρήστη αποτελέσματα που είναι διαφοροποιημένα μεταξύ τους και την ίδια στιγμή καλύπτουν όλο το σύνολο των αποτελεσμάτων του ερωτήματος στη βάση. Η προσέγγιση που γίνεται για την επίλυση του προβλήματος με αυτό τον τρόπο εμπεριέχει την μετατροπή του DisC αλγορίθμου σε τρεις παραλλαγές, που επιλέγουν αποτελέσματα για το τελικό σύνολο με βάση τρία διαφορετικά κριτήρια. Εκτός από τον παραπάνω αλγόριθμο, γίνεται προσπάθεια προσέγγισης του προβλήματος με μια παραλλαγή του αλγορίθμου [20] που λύνει το Maximum Coverage πρόβλημα, το οποίο είναι NPhard, όπως και το αρχικό πρόβλημα αυτής της μελέτης. Με αυτή τη μέθοδο, στόχος είναι να δημιουργηθεί μια κατάταξη των αποτελεσμάτων που επέστρεψε το ερώτημα. Αυτή η κατάταξη πρέπει να είναι τέτοια ώστε οσαδήποτε αποτελέσματα επιλεγούν να παρουσιαστούν στο χρήστη, να καλύπτουν σε κάθε περίπτωση σε μέγιστο βαθμό το σύνολο με τα αποτελέσματα του αρχικού ερωτήματος. Η κάλυψη σε αυτό το σημείο έγκειται στην ομοιότητα των αποτελεσμάτων σε σχέση με τα υπόλοιπα. Η καινοτομία που εισάγει αυτή η εργασία είναι η υλοποίηση των παραπάνω αλγορίθμων, και ειδικά του DisC Diversity, με τέτοιο τρόπο ώστε να μπορούν να εκτελεστούν παράλληλα σε ένα κατανεμημένο περιβάλλον. Με αυτό τον τρόπο θέλουμε να πετύχουμε το ζητούμενο της εργασίας, που είναι η επεξεργασία μεγάλου όγκου δεδομένων. Για αυτό το σκοπό χρησιμοποιούμε τη λογική του Map Reduce, που μπορεί να εφαρμοστεί μέσω της πλατφόρμας του Hadoop. Το Hadoop αποτελείται από ένα τρόπο δομής και διαχείρισης ενός αρχείου συστήματος και ένα τρόπο επικοινωνίας μεταξύ διασυνδεδεμένων υπολογιστών, ώστε να μπορεί να εκτελεστεί πάνω του ένα πρόγραμμα που έχει τη λογική του Map Reduce. Το Hadoop είναι λογισμικό ανοιχτού κώδικα και έχει δημιουργηθεί από την Apache, βασισμένο σε μια ερευνητική εργασία της Google η οποία περιγράφει το Map Reduce και το Google File System, που δημιουργήθηκαν στα εργαστήριά της. Για τα πειράματά μας χρησιμοποιούμε τεχνητά αλλά και πραγματικά σύνολα δεδομένων, που προσομοιώνουν σύνολα αποτελεσμάτων που έχουν επιστραφεί από ερωτήματα σε κάποια βάση δεδομένων. Τα τεχνητά σύνολα είναι κατασκευασμένα με τέτοιο τρόπο ώστε να αντιπροσωπεύουν δύο μεγάλες κατηγορίες. Η διαφοροποίησή τους έγκειται στην κατανομή των δεδομένων όσον αφορά τα χαρακτηριστικά τους. Υπάρχουν σύνολα δεδομένων που είναι φτιαγμένα με τυχαίο τρόπο αλλά και άλλα που περιέχουν λογικές ομάδες αποτελεσμάτων που έχουν πιο σχετικά χαρακτηριστικά σε σχέση με τα υπόλοιπα, δημιουργώντας συστάδες. Πάνω σε αυτή τη διαφοροποίηση γίνεται μια επιπλέον μελέτη για το αν και κατά πόσον ένας διαφορετικός διαχωρισμός των δεδομένων πριν την εκτέλεση του βασικού αλγορίθμου μπορεί να οδηγήσει σε καλύτερα αποτελέσματα. Ο διαχωρισμός που επιχειρείται γίνεται με την χρήση του αλγορίθμου συσταδοποίησης kmeans. Η επιτυχία των αλγορίθμων κρίνεται από το ποσοστό ευστοχίας του συνόλου δεδομένων που παράγουν ως αποτέλεσμα. Η ευστοχία ή αστοχία του τελικού συνόλου δεδομένων υπολογίζεται με βάση το ποσοστό των λανθασμένων αποτελεσμάτων που περιλαμβάνονται σε αυτό. Ένα αποτέλεσμα χαρακτηρίζεται ως λανθασμένο, αν έχει όμοια χαρακτηριστικά με κάποιο άλλο που βρίσκεται και αυτό μέσα στο τελικό σύνολο, που θα παρουσιαστεί στο χρήστη. Αυτό το αποτέλεσμα είναι περιττό και αποτελεί αστοχία του αλγορίθμου. Η αξιολόγηση των αποτελεσμάτων βασίζεται κυρίως στο χρόνο εκτέλεσης των αλγορίθμων αλλά και στην απόδοσή τους, η οποία κρίνεται από το μέγεθος του τελικού συνόλου δεδομένων που παράγεται σε σχέση με το αρχικό αλλά και από το πόσο εύστοχο είναι. Σε πρώτη φάση γίνεται μια ξεχωριστή αξιολόγηση των αλγορίθμων πάνω στην ίδια πειραματική βάση, ενώ ακολουθεί μια σύγκριση των δύο κατηγοριών αλγορίθμων. Στο στάδιο της σύγκρισης παρατηρείται η επίπτωση που έχουν διάφορες παράμετροι που έχουμε θέσει στην απόδοση των αλγορίθμων. Οι παράμετροι αυτοί είναι η πληθικότητα του αρχικού συνόλου δεδομένων, η δομή και η κατανομή του αρχικού συνόλου δεδομένων, ο αριθμός των Mappers και Reducers που χρησιμοποιούνται για την εκτέλεση των πειραμάτων, όπως και η μετρική που έχουμε θέσει για τον υπολογισμό της ομοιότητας μεταξύ δύο αποτελεσμάτων. Μετά από την εκτέλεση των παραπάνω πειραμάτων και την επεξεργασία των αποτελεσμάτων τους με βάση τα κριτήρια αξιολόγησης που έχουμε θέσει, κρίνουμε αν και κατά πόσον κάποιος αλγόριθμος προτιμάται, ώστε να εφαρμοστεί για την επεξεργασία ενός εκτεταμένου συνόλου δεδομένων, με σκοπό να παρουσιαστεί στο χρήστη ένα αρκετά ποικιλόμορφο, διαφοροποιημένο και πληροφοριακό σύνολο αποτελεσμάτων.
Μια αναζήτηση ενός χρήστη σε μια βάση δεδομένων κρίνεται από το αν και κατά πόσο το αποτέλεσμα αυτής της αναζήτησης θα βοηθήσει το χρήστη να βρει γρήγορα και εύκολα αυτό που ψάχνει. Η ποικιλομορφία των αποτελεσμάτων που παρουσιάζονται μετά από μια αναζήτηση σε μια βάση δεδομένων είναι κάτι που έχει αυξανόμενο επιστημονικό ενδιαφέρον τελευταία. Για να γίνει λοιπόν πιο ποιοτικό και ελκυστικό ένα αποτέλεσμα αναζήτησης επιδέχεται κάποιας επεξεργασίας, πριν την τελική παρουσίαση του στο χρήστη. Η επεξεργασία αυτή καθιστά το αποτέλεσμα της αναζήτησης πιο αξιόπιστο, αφού παρουσιάζει ένα υποσύνολο του αρχικού αποτελέσματος, το οποίο παραθέτει αντιπροσωπευτικά δείγματα και είναι επίσης τόσο διαφοροποιημένο, ώστε τα αποτελέσματα που θα εμφανιστούν στο χρήστη να είναι ποικιλόμορφα και εύστοχα. Μέχρι στιγμής έχουν γίνει διάφορες απόπειρες για τη σχεδίαση ενός μοντέλου που θα παράγει αποτελέσματα με τις παραπάνω ιδιότητες. Κάθε απόπειρα θέτει ένα διαφορετικό ορισμό για τη ποικιλομορφία των δεδομένων, κοιτάζοντας το πρόβλημα από διαφορετική οπτική γωνία. Σε αυτή την εργασία μελετάται ο αλγόριθμος [8] του DisC Diversity. Ανάμεσα στις διάφορες θεωρήσεις, επιλέξαμε να μελετήσουμε τον αλγόριθμο DisC διότι καλύπτει καλύτερα τις ανάγκες του προβλήματος που έχουμε θέσει, επιστρέφοντας στο χρήστη αποτελέσματα που είναι διαφοροποιημένα μεταξύ τους και την ίδια στιγμή καλύπτουν όλο το σύνολο των αποτελεσμάτων του ερωτήματος στη βάση. Η προσέγγιση που γίνεται για την επίλυση του προβλήματος με αυτό τον τρόπο εμπεριέχει την μετατροπή του DisC αλγορίθμου σε τρεις παραλλαγές, που επιλέγουν αποτελέσματα για το τελικό σύνολο με βάση τρία διαφορετικά κριτήρια. Εκτός από τον παραπάνω αλγόριθμο, γίνεται προσπάθεια προσέγγισης του προβλήματος με μια παραλλαγή του αλγορίθμου [20] που λύνει το Maximum Coverage πρόβλημα, το οποίο είναι NPhard, όπως και το αρχικό πρόβλημα αυτής της μελέτης. Με αυτή τη μέθοδο, στόχος είναι να δημιουργηθεί μια κατάταξη των αποτελεσμάτων που επέστρεψε το ερώτημα. Αυτή η κατάταξη πρέπει να είναι τέτοια ώστε οσαδήποτε αποτελέσματα επιλεγούν να παρουσιαστούν στο χρήστη, να καλύπτουν σε κάθε περίπτωση σε μέγιστο βαθμό το σύνολο με τα αποτελέσματα του αρχικού ερωτήματος. Η κάλυψη σε αυτό το σημείο έγκειται στην ομοιότητα των αποτελεσμάτων σε σχέση με τα υπόλοιπα. Η καινοτομία που εισάγει αυτή η εργασία είναι η υλοποίηση των παραπάνω αλγορίθμων, και ειδικά του DisC Diversity, με τέτοιο τρόπο ώστε να μπορούν να εκτελεστούν παράλληλα σε ένα κατανεμημένο περιβάλλον. Με αυτό τον τρόπο θέλουμε να πετύχουμε το ζητούμενο της εργασίας, που είναι η επεξεργασία μεγάλου όγκου δεδομένων. Για αυτό το σκοπό χρησιμοποιούμε τη λογική του Map Reduce, που μπορεί να εφαρμοστεί μέσω της πλατφόρμας του Hadoop. Το Hadoop αποτελείται από ένα τρόπο δομής και διαχείρισης ενός αρχείου συστήματος και ένα τρόπο επικοινωνίας μεταξύ διασυνδεδεμένων υπολογιστών, ώστε να μπορεί να εκτελεστεί πάνω του ένα πρόγραμμα που έχει τη λογική του Map Reduce. Το Hadoop είναι λογισμικό ανοιχτού κώδικα και έχει δημιουργηθεί από την Apache, βασισμένο σε μια ερευνητική εργασία της Google η οποία περιγράφει το Map Reduce και το Google File System, που δημιουργήθηκαν στα εργαστήριά της. Για τα πειράματά μας χρησιμοποιούμε τεχνητά αλλά και πραγματικά σύνολα δεδομένων, που προσομοιώνουν σύνολα αποτελεσμάτων που έχουν επιστραφεί από ερωτήματα σε κάποια βάση δεδομένων. Τα τεχνητά σύνολα είναι κατασκευασμένα με τέτοιο τρόπο ώστε να αντιπροσωπεύουν δύο μεγάλες κατηγορίες. Η διαφοροποίησή τους έγκειται στην κατανομή των δεδομένων όσον αφορά τα χαρακτηριστικά τους. Υπάρχουν σύνολα δεδομένων που είναι φτιαγμένα με τυχαίο τρόπο αλλά και άλλα που περιέχουν λογικές ομάδες αποτελεσμάτων που έχουν πιο σχετικά χαρακτηριστικά σε σχέση με τα υπόλοιπα, δημιουργώντας συστάδες. Πάνω σε αυτή τη διαφοροποίηση γίνεται μια επιπλέον μελέτη για το αν και κατά πόσον ένας διαφορετικός διαχωρισμός των δεδομένων πριν την εκτέλεση του βασικού αλγορίθμου μπορεί να οδηγήσει σε καλύτερα αποτελέσματα. Ο διαχωρισμός που επιχειρείται γίνεται με την χρήση του αλγορίθμου συσταδοποίησης kmeans. Η επιτυχία των αλγορίθμων κρίνεται από το ποσοστό ευστοχίας του συνόλου δεδομένων που παράγουν ως αποτέλεσμα. Η ευστοχία ή αστοχία του τελικού συνόλου δεδομένων υπολογίζεται με βάση το ποσοστό των λανθασμένων αποτελεσμάτων που περιλαμβάνονται σε αυτό. Ένα αποτέλεσμα χαρακτηρίζεται ως λανθασμένο, αν έχει όμοια χαρακτηριστικά με κάποιο άλλο που βρίσκεται και αυτό μέσα στο τελικό σύνολο, που θα παρουσιαστεί στο χρήστη. Αυτό το αποτέλεσμα είναι περιττό και αποτελεί αστοχία του αλγορίθμου. Η αξιολόγηση των αποτελεσμάτων βασίζεται κυρίως στο χρόνο εκτέλεσης των αλγορίθμων αλλά και στην απόδοσή τους, η οποία κρίνεται από το μέγεθος του τελικού συνόλου δεδομένων που παράγεται σε σχέση με το αρχικό αλλά και από το πόσο εύστοχο είναι. Σε πρώτη φάση γίνεται μια ξεχωριστή αξιολόγηση των αλγορίθμων πάνω στην ίδια πειραματική βάση, ενώ ακολουθεί μια σύγκριση των δύο κατηγοριών αλγορίθμων. Στο στάδιο της σύγκρισης παρατηρείται η επίπτωση που έχουν διάφορες παράμετροι που έχουμε θέσει στην απόδοση των αλγορίθμων. Οι παράμετροι αυτοί είναι η πληθικότητα του αρχικού συνόλου δεδομένων, η δομή και η κατανομή του αρχικού συνόλου δεδομένων, ο αριθμός των Mappers και Reducers που χρησιμοποιούνται για την εκτέλεση των πειραμάτων, όπως και η μετρική που έχουμε θέσει για τον υπολογισμό της ομοιότητας μεταξύ δύο αποτελεσμάτων. Μετά από την εκτέλεση των παραπάνω πειραμάτων και την επεξεργασία των αποτελεσμάτων τους με βάση τα κριτήρια αξιολόγησης που έχουμε θέσει, κρίνουμε αν και κατά πόσον κάποιος αλγόριθμος προτιμάται, ώστε να εφαρμοστεί για την επεξεργασία ενός εκτεταμένου συνόλου δεδομένων, με σκοπό να παρουσιαστεί στο χρήστη ένα αρκετά ποικιλόμορφο, διαφοροποιημένο και πληροφοριακό σύνολο αποτελεσμάτων.
Περιγραφή
Λέξεις-κλειδιά
Κατανεμημένα συστήματα, Παράλληλη υλοποίηση αλγορίθμων, Ποικιλομορφία, Hadoap, Map-reduce, Diversification, Disc
Θεματική κατηγορία
Algorithms
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Πιτουρά, Ευαγγελία
Εξεταστική επιτροπή
Πιτουρά, Ευαγγελία
Μαμουλής, Νικόλαος
Μαγκούτης, Κωνσταντίνος
Μαμουλής, Νικόλαος
Μαγκούτης, Κωνσταντίνος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογράφία : σ. 55-56
Ονόματα συντελεστών
Αριθμός σελίδων
59 σ.