Aviez-vous entendu parler des Bloom Filter avant aujourd'hui ? En tout cas, moi non. Il s'agit d'une structure de données permettant de stocker l'appartenance ou non d'un objet à un ensemble de manière efficace. L'approche naive dans ce cas est de stocker tous les objets dans l'ensemble, mais cela demande beaucoup de place. Bloom Filter permet de faire cela en utilisant extrêmement peu de place. Je vous laisse découvrir comment.
Pour info, c'est le genre de structure utilisée par Twitter pour savoir quels tweets appartiennent à qui. Voir ici pour plus d'infos : https://speakerdeck.com/johnynek/algebra-for-analytics