Μέτρηση Αντικείμενα σε ροή δεδομένων - ανδρείκελα

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

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

Εφαρμόζετε τη λύση σε αυτό το πρόβλημα, Count-Min Sketch, σε μια ροή δεδομένων. Απαιτεί μόνο ένα δελτίο δεδομένων και αποθηκεύει όσο το δυνατόν λιγότερες πληροφορίες. Αυτός ο αλγόριθμος εφαρμόζεται σε πολλές πραγματικές καταστάσεις (όπως η ανάλυση της κυκλοφορίας δικτύου ή η διαχείριση ροής κατανεμημένων δεδομένων). Η συνταγή απαιτεί τη χρήση μιας δέσμης λειτουργιών κατακερματισμού, καθεμία από τις οποίες συνδέεται με ένα διάνυσμα δυαδικών ψηφίων, κατά τρόπο που μοιάζει με ένα φίλτρο Bloom, όπως φαίνεται στο σχήμα:

1. Αρχικοποιήστε όλους τους διανύσματα δυαδικών ψηφίων σε μηδενικά σε όλες τις θέσεις.
2. Εφαρμόστε τη συνάρτηση κατακερματισμού για κάθε διάνυσμα δυαδικών ψηφίων όταν λαμβάνετε ένα αντικείμενο από μια ροή. Χρησιμοποιήστε την αριθμητική διεύθυνση που προκύπτει για να αυξήσετε την τιμή στη συγκεκριμένη θέση.
3. Εφαρμόστε τη συνάρτηση κατακερματισμού σε ένα αντικείμενο και ανακτήστε την τιμή στη σχετική θέση όταν σας ζητηθεί να εκτιμήσετε τη συχνότητα ενός αντικειμένου. Από όλες τις τιμές που λαμβάνονται από τους διανύσματα δυαδικών ψηφίων, παίρνετε το μικρότερο ως τη συχνότητα του ρεύματος.

Πώς ενημερώνονται οι τιμές σε μια σμίκρυνση σε μετρήσεις.

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