✖

HyperLogLog: Πώς να εκτιμήσεις με μεγάλη ακρίβεια το πλήθος των μοναδικών τιμών

Η σειρά για τους αλγορίθμους εκτίμησης του πλήθους των μοναδικών τιμών σε ένα πολυσύνολο συνεχίζεται με ένα άρθρο για τον αλγόριθμο HyperLogLog, που είναι state of the art. Όλες οι ιδέες πίσω από αυτόν τον αλγόριθμο όμως προέρχονται από τον LogLog που περιγράψαμε νωρίτερα, γι' αυτό, αν θέλεις να συνεχίσεις το διάβασμα, φρόντισε να γνωρίζεις καλά τον LogLog.

Ο αλγόριθμος LogLog είχε δύο βασικά προβλήματα:

Ακραίες τιμές

Η τελική εκτίμηση του LogLog είναι πολύ ευαίσθητη στις ακραίες τιμές (outliers), δηλαδή σε τιμές που απέχουν πολύ από τις υπόλοιπες. Τυπικά συμβαίνει τα περισσότερα μέγιστα μήκη επιθεμάτων μηδενικών για κάθε ομάδα να είναι περίπου ίδια, για παράδειγμα να κυμαίνονται από 12 έως 15, αλλά μετά μπαμ – και ένα επίθεμα μηδενικών έχει μήκος 27. Αυτή η μεγάλη διαφορά χαλάει την τελική εκτίμηση του πλήθους των μοναδικών, επειδή ο κλασικός αριθμητικός μέσος όρος δεν τα καταφέρνει πολύ καλά με αυτό. Ουσιαστικά λειτούργησε η ίδια αρχή όπως όταν μερικά ανώτατα στελέχη και διευθυντές ανεβάζουν με τους υψηλούς μισθούς τους τον μέσο μισθό στη χώρα.

Οι συγγραφείς του αλγορίθμου προσπάθησαν να το λύσουν απαλλασσόμενοι από τις ακραίες τιμές και δεν υπολόγισαν στον μέσο όρο μερικά από τα μεγαλύτερα μέγιστα, αλλά αυτό δεν ήταν πολύ καλή λύση. Αργότερα δοκίμασαν μια άλλη διαδικασία – αντί για τον αριθμητικό μέσο χρησιμοποίησαν τον αρμονικό, που έχει πολύ καλύτερες ιδιότητες όταν έχουμε τιμές που απέχουν από τον μέσο.

Πολύ κακά αποτελέσματα για μικρές πληθικότητες

Ο LogLog έχει απαίσια αποτελέσματα όταν πρέπει να εκτιμήσει την πληθικότητα μικρών πολυσυνόλων. Αν το πολυσύνολο έχει λίγα μόνο μοναδικά στοιχεία, ο LogLog μας επιστρέφει παράλογα μεγάλη εκτίμηση. Οι συγγραφείς το έλυσαν έξυπνα – όταν στην είσοδο έχουμε πολυσύνολο με χαμηλή πληθικότητα, δεν χρησιμοποιείται ο αλγόριθμος LogLog, αλλά ένας εντελώς διαφορετικός, και συγκεκριμένα ο παλιός γνωστός Linear counting. Ναι, αλλά πώς θα καταλάβουμε ότι στην είσοδο έχουμε πολυσύνολο με μικρή πληθικότητα, όταν ακριβώς την πληθικότητα δεν τη γνωρίζουμε;

Αφήνουμε τον LogLog να εκτιμήσει το πλήθος των μοναδικών στοιχείων και, όταν διαπιστώσουμε ότι αυτή η εκτίμηση είναι σχετικά χαμηλή, την απορρίπτουμε και την υπολογίζουμε ξανά με τον αλγόριθμο Linear counting. Ας θυμηθούμε γρήγορα πώς λειτουργεί το Linear counting. Στην αρχή δημιουργούμε έναν μηδενικό (δυαδικό) πίνακα προκαθορισμένου μεγέθους, τυπικά δύναμη του δύο. Περνάμε από όλα τα στοιχεία του πολυσυνόλου, υπολογίζουμε το hash τους και το μετατρέπουμε σε έναν ακέραιο αριθμό i από το διάστημα 0 έως το μήκος του πίνακα μείον ένα. Στη θέση i του πίνακα αποθηκεύουμε έναν άσο. Στο τέλος μετράμε τα μηδενικά και τους άσους του πίνακα και με έναν απλό τύπο εκτιμούμε την πληθικότητα.

Ο αλγόριθμος LogLog όμως δεν χρησιμοποιεί κανέναν δυαδικό πίνακα στον οποίο να «αποθηκεύει» τα hash που υπολόγισε. Αντί γι' αυτό χρησιμοποιεί έναν πίνακα στον οποίο κρατά τα μέγιστα μήκη των επιθεμάτων. Ο πίνακας μπορεί να μοιάζει για παράδειγμα έτσι:

[2, 5, 9, 0, 5, 4, 4, 0]

όπου κάθε αριθμός δηλώνει το μέγιστο μήκος του επιθέματος μηδενικών στην αντίστοιχη ομάδα των hash που υπολογίστηκαν. Μια μη μηδενική τιμή στη θέση i σημαίνει όμως αναγκαστικά ότι ανάμεσα στις τιμές του πολυσυνόλου υπάρχει στοιχείο του οποίου το (τριών bit) hash είναι ίσο με i. Με άλλα λόγια, αυτόν τον πίνακα μπορούμε να τον μετατρέψουμε σε δυαδικό πίνακα για το linear counting αφήνοντας τα μηδενικά και μετατρέποντας κάθε θετικό αριθμό σε άσο. Από τον προηγούμενο πίνακα θα παίρναμε έτσι τον δυαδικό πίνακα:

[1, 1, 1, 0, 1, 1, 1, 0]

Τώρα μπορούμε να εφαρμόσουμε τον αλγόριθμο Linear counting και να εκτιμήσουμε με αυτόν την πληθικότητα.

Υπάρχει όμως ένα πρόβλημα. Εμείς στον πίνακα αποθηκεύουμε το μέγιστο επίθεμα μηδενικών, αλλά τι γίνεται αν σε κάποια ομάδα τιμών όλα τα hash τελειώνουν σε άσο; Αν για παράδειγμα χρησιμοποιήσουμε τα τελευταία τρία bit ως αναγνωριστικό της ομάδας στην οποία ανήκει το hash, τότε το μήκος του επιθέματος μηδενικών αυτού του hash «01001100» θα ήταν μηδέν – επειδή το διάνυσμα «01001» τελειώνει σε άσο. Στον πίνακα των μεγίστων θα αποθηκεύαμε έτσι στη θέση 4 (1002=410) μηδέν. Στον αλγόριθμο linear counting αυτό θα εμφανιζόταν ως εξής: δεν βρήκαμε τιμή που να έχει ως hash το τέσσερα, κάτι που δεν είναι αλήθεια.

Γι' αυτό τροποποιούμε τον αλγόριθμο ώστε να μην αποθηκεύει στον πίνακα των μεγίστων το μήκος του μεγαλύτερου επιθέματος μηδενικών, αλλά τον δείκτη του «πρώτου άσου από τα δεξιά» (για την ακρίβεια – η αρίθμηση ξεκινά από το ένα), που είναι το ίδιο με το να προσθέσουμε ένα στο μήκος του επιθέματος μηδενικών. Έτσι πετυχαίνουμε το μηδέν στη θέση i να σημαίνει ότι καμία τιμή δεν έχει hash ίσο με i και τότε μπορούμε να χρησιμοποιήσουμε τον πίνακα για το linear counting.

Υλοποίηση του HyperLogLog

Βήμα βήμα:

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

Η συνάρτηση alpha επιστρέφει τη διόρθωση για την εκτίμηση που υπολογίστηκε, αυτό το ξέρουμε από την προηγούμενη φορά, μόνο που στην περίπτωση του HyperLogLog το alpha έχει άλλη τιμή ανάλογα με το πλήθος των ομάδων.

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

Η συνάρτηση που επιστρέφει το πλήθος των μηδενικών bit στο τέλος του αριθμού.

def count_maxims(values, k):
    num_buckets = 2 ** k  
    max_zeroes = [0] * num_buckets

    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

Η συνάρτηση που περνά από όλες τις τιμές, τις χωρίζει σε num_buckets ομάδες και για κάθε ομάδα υπολογίζει τον δείκτη του πρώτου άσου από τα δεξιά (το μήκος του μέγιστου επιθέματος μηδενικών συν ένα).

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

Ελαφρώς τροποποιημένη συνάρτηση για τον υπολογισμό του αλγορίθμου Linear counting.

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

Η κύρια συνάρτηση, που τα συνδυάζει όλα. Πρώτα υπολογίζει την εκτίμηση με τον τροποποιημένο LogLog, αντί για αριθμητικό μέσο όρο χρησιμοποιεί στην τέταρτη γραμμή τον αρμονικό και στο τέλος εφαρμόζει τη διόρθωση με το Linear counting, αν η εκτίμηση που υπολογίστηκε είναι μικρότερη από 2,5 φορές το πλήθος των ομάδων (εδώ περιμένουμε ότι η συνήθης εκτίμηση του LogLog θα είναι χειρότερη από ό,τι αν χρησιμοποιούσαμε το Linear counting) και αν στον πίνακα των μεγίστων υπάρχει τουλάχιστον ένα μηδέν (έναν πίνακα που έχει μόνο άσους δεν μπορούμε να τον χρησιμοποιήσουμε στο Linear counting, βλέπε προηγούμενο άρθρο). Και ποια είναι τα αποτελέσματα του HyperLogLog;

Τρέχουμε κώδικα δοκιμής που εκτιμά την πληθικότητα συνόλων με πληθικότητα διαδοχικά 10, 100, …, 1.000.000:

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

Αποτελέσματα:

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

Βλέπουμε ότι τα αποτελέσματα αποκλίνουν πάντα από το σωστό κατά λιγότερο από ένα τοις εκατό. Και αυτό είναι καλό!

Περαιτέρω βελτιώσεις του HyperLogLog

Ο HyperLogLog γνώρισε αρκετές ακόμη ενδιαφέρουσες βελτιώσεις. Ένα από τα προβλήματα που απομένουν είναι η υψηλή απαίτηση σε μνήμη. Αυτό ακούγεται περίεργο, αφού την προηγούμενη φορά εκθειάσαμε την απαίτηση σε μνήμη και υπολογίσαμε ότι για την αποθήκευση του πίνακα των μεγίστων μας αρκούν 768 byte. Το πρόβλημα όμως εμφανίζεται αν θέλεις να μετρήσεις την πληθικότητα όχι ενός τεράστιου πολυσυνόλου, αλλά παράλληλα αρκετών εκατομμυρίων μικρών πολυσυνόλων, ή αν θέλεις να φυλάς αυτούς τους πίνακες μεγίστων σε βάση δεδομένων για κάποια μεταγενέστερα κόλπα.

Αν για παράδειγμα μετρούσαμε ταυτόχρονα την πληθικότητα ενός δισεκατομμυρίου πολυσυνόλων, με την τρέχουσα υλοποίηση θα χρειαζόμασταν 1.000.000.000 επί 768 byte, δηλαδή 768 GB. Από τη μία πλευρά δεν είναι άσχημα … αλλά από την άλλη μπορούμε να υλοποιήσουμε τον HyperLogLog καλύτερα.

Αραιή αναπαράσταση

Ας φανταστούμε ότι ορίζουμε k=12, δηλαδή χρησιμοποιούμε 12 bit για την αναγνώριση των ομάδων και έχουμε επομένως 212 διαφορετικές ομάδες hash. Στην αρχή του αλγορίθμου πρέπει να δεσμεύσουμε πίνακα μήκους 4096 (βλέπε γραμμή 3 της συνάρτησης count_maxims). Και ας πούμε ότι το πολυσύνολό μας έχει τρία διαφορετικά στοιχεία. Αυτό σημαίνει ότι στον πίνακα σε τρεις διαφορετικές θέσεις θα ορίσουμε κάποια τιμή και οι υπόλοιπες 4093 τιμές του πίνακα θα παραμείνουν μηδενικές, τις υπόλοιπες 4093 απλώς δεν τις χρησιμοποιήσαμε καθόλου. Αυτό δεν είναι πολύ αποδοτικό, έτσι δεν είναι;

Για να αποφύγουμε να έχουμε πίνακα που θα είναι κατά το μεγαλύτερο μέρος μηδενικός και αχρησιμοποίητος, αλλά θα καταλαμβάνει παρ' όλα αυτά πολύτιμο χώρο στη μνήμη, μπορούμε στην αρχή να αποθηκεύουμε τις τιμές ως ζεύγη [δείκτης, τιμή]. Ένα παράδειγμα για καλύτερη κατανόηση. Αυτόν τον πίνακα

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

μπορούμε να τον αναπαραστήσουμε πολύ πιο οικονομικά ως προς τη μνήμη ως δύο ζεύγη:

[0, 7], [4, 12]

Αντί να έχουμε στη μνήμη δεσμευμένο ένα σωρό αχρησιμοποίητου χώρου, μπορούμε σταδιακά να δεσμεύουμε μόνο τον χώρο που πραγματικά χρειαζόμαστε. Αυτή την αναπαράσταση την ονομάζουμε αραιή (sparse). Ωστόσο κάποια στιγμή αυτή η αναπαράσταση θα ήταν πιο απαιτητική σε μνήμη από την αποθήκευση σε πίνακα – τότε μπορούμε να μετατρέψουμε την αραιή αναπαράσταση σε κλασικό πίνακα χωρίς απώλεια πληροφορίας.

Μετατοπίσεις (offsets)

Η πράξη έδειξε ότι όλες οι τιμές του πίνακα είναι περίπου ίδιες. Ο πίνακας των μεγίστων συνήθως μοιάζει για παράδειγμα έτσι:

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

Όλες οι τιμές κυμαίνονται κάπου γύρω από τον αριθμό 13. Μια ακόμη στρατηγική για να μειώσουμε το μέγεθος ενός τέτοιου πίνακα είναι να αφαιρέσουμε από κάθε στοιχείο μια σταθερή τιμή και να την απομνημονεύσουμε. Μπορούμε να αφαιρέσουμε για παράδειγμα το οκτώ:

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

Τώρα κάθε τιμή του πίνακα καταναλώνει λιγότερη μνήμη – στον πρώτο πίνακα πρέπει να αποθηκεύουμε αριθμούς από το 0 έως το 15, για τους οποίους χρειαζόμαστε 4 bit, ενώ για τον δεύτερο πίνακα μας αρκούν 3 bit, επειδή αποθηκεύουμε μόνο αριθμούς από το 0 έως το 7. Φυσικά αυτό προϋποθέτει υλοποίηση του πίνακα σε επίπεδο μεμονωμένων bit. Όταν θέλουμε να διαβάσουμε τιμές από τον πίνακα, πρέπει να προσθέσουμε πίσω την τιμή που σημειώσαμε.

…και ένας σωρός άλλες βελτιώσεις. Η έρευνα σε αυτόν τον τομέα συνεχίζεται ακόμη, οπότε σίγουρα μπορούμε να περιμένουμε και άλλες ενδιαφέρουσες ιδέες. Την επόμενη φορά θα πούμε κάτι για την ένωση και την τομή διανυσμάτων HyperLogLog και κάποια στιγμή στο κοντινό μέλλον θα πούμε γιατί μπορεί να μας φανεί χρήσιμο να αποθηκεύουμε δισεκατομμύρια διανύσματα HyperLogLog.

Σύνδεσμοι και πηγές

Κεφάλαια: Linear counting, Min Value, LogLog, HyperLogLog