Αποδοτικός Σε Χώρο Και Χρόνο Υπολογισμός Των Βαθμών Των Κόμβων Γράφων Με Χρήση Πιθανοτικών Τεχνικών Data Sketching

Abstract

Η έννοια Big Data εμφανίζεται σε ολοένα και περισσότερους κλάδους στις μέρες μας. Η ποσότητα της πληροφορίας που παράγεται καθημερινά αυξάνει συνεχώς και μάλιστα με ρυθμούς ταχύτερους απ’ ότι μεγαλώνουν τα διαθέσιμα μέσα αποθήκευσης ή βελτιώνονται οι γνωστές τεχνικές για την ανάλυση και την επεξεργασία τους.Η ανάγκη λοιπόν για τεχνικές που να επιτυγχάνουν ανάλυση μεγάλων ποσοτήτων δεδομένων σε υψηλές ταχύτητες και καταλαμβάνοντας όσο το δυνατόν λιγότερο χώρο κρίνεταικρίσιμη. Για το σκοπό αυτό έχουν προταθεί διάφορες λύσεις. Μία εξ’ αυτών, και αυτή με την οποία θα ασχοληθούμε στην παρούσα εργασία, είναι το Data Sketching. Η τεχνική αυτή επιτρέπει την αποθήκευση και ανάκτηση πληροφορίας με τρόπο πιθανοτικό, απαιτώντας πολύ μικρό χώρο συγκριτικά με πιο "παραδοσιακές" μεθόδους, και μάλιστα επιτυγχάνει κάτι τέτοιο διατηρώντας εξαιρετικά επίπεδα χρονικής πολυπλοκότητας. Το πρόβλημα που θα χρησιμοποιηθεί ως οδηγός στην προσπάθεια βαθύτερης κατανόησης και στην έρευνα γύρω από το Data Sketching είναι αυτό του υπολογισμού των in-degrees τωνκόμβων ενός γράφου (κοινωνικού γράφου στη συγκεκριμένη περίπτωση). Για το σκοπό αυτό, επιλέγουμε τη μέθοδο Count Min Sketch η οποία επιτρέπει, για κάθε κόμβο, την αποθήκευση του πλήθους των εισερχόμενων σε αυτόν ακμών, με τρόπο πιθανοτικό, επιτυγχάνοντας υψηλά επίπεδα απόδοσης. Καθώς η παραπάνω μέθοδος απαιτεί κατάλληλη, σε σχέση με τα χαρακτηριστικά του γράφου στον οποίο εφαρμόζεται, επιλογή των παραμέτρων της προκειμένου να επιστρέψει καλά αποτελέσματα, κρίνεται χρήσιμη η αναζήτηση ενός τρόπου που να μην απαιτεί πρότερη γνώση του γράφου, αλλά να αποτελεί universal λύση. Προτείνεται εδώ ένας αλγόριθμος ο οποίος δεσμεύοντας αρχικά μικρό ποσοστό της μνήμης, αυξάνει δυναμικά το χώρο που καταλαμβάνει ούτως ώστε ναδιατηρείται η απαραίτητη ακρίβεια των αποτελεσμάτων. Κάτι τέτοιο αυξάνει τις απαιτήσεις σε μνήμη, όμως ο τελικός χώρος που καταλαμβάνεται εξακολουθεί να είναι μικρότερος απ’ αυτόν που θα απαιτούνταν από μια ντετερμινιστική δομή δεδομένων, ενώ ο χρόνος και η ακρίβεια προσεγγίζουν τα κλασσικά επίπεδα μιας Count Min υλοποίησης που εφαρμόζεται σε γνωστόγράφο.Οι κοινωνικοί γράφοι ακολουθούν Power Law κατανομή. Το συγκεκριμένο τους χαρακτηριστικό, όπως θα φανεί και στη συνέχεια, καθιστά ιδιαίτερα υψηλές τις απαιτήσεις σεακρίβεια του αλγορίθμου. Έτσι, τα αποτελέσματα της παρούσας εργασίας μπορούν, με μικρές αλλαγές, να γενικευτούν και να χρησιμοποιηθούν και για άλλες περιπτώσεις, πλην των κοινωνικών δικτύων, οι οποίες εμφανίζουν παρόμοιες ανάγκες σε ακρίβεια.