Filtre de Bloom | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

En informatique, et plus précisément en algorithmique, un filtre de Bloom est une structure de données inventée par Burton Howard Bloom en 1970. C'est une implémentation du type abstrait Ensemble. Cette structure est probabiliste, c'est-à-dire qu'elle utilise des probabilités, et que sa correction est probabiliste. Plus précisément, lors du test de la présence d'un élément dans un ensemble, un filtre de Bloom permet de savoir : avec certitude l'absence d'un élément (il ne peut pas y avoir de faux négatif) ; avec une certaine probabilité la présence d'un élément (il peut y avoir des faux positifs). La taille d'un filtre de Bloom est fixe et indépendante du nombre d'éléments contenus, ce qui en fait une structure très compacte. L'inconvénient est toutefois qu'il y a d'autant plus de faux positifs qu'il y a d'éléments dans la structure. Le principe du filtre est le même que pour le hachage. Un filtre de Bloom est constituée d'un tableau de bits de taille m, ainsi qu'une collection de k fonctions de hachage . Chaque fonction de hachage associe tout élément à une case du tableau. En général, k est une constante qui dépend du taux de faux positifs souhaité, tandis que m est proportionnel à k et au nombre d'éléments à ajouter. Soit U l'univers de tous les éléments que pourrait contenir l'ensemble considéré. Par exemple, U est l'ensemble des entiers sur 32 bits, ou un ensemble de mots. Le filtre a deux composantes : T : un tableau de bits de taille m dont chaque case est initialisée à 0. (indexé de 1 à m) k fonctions de hachage de . Pour ajouter un élément , on met des 1 dans les cases d'indice . Pour tester si un élément est présent, on vérifie que les cases d'indice contiennent toutes un 1. Il se peut que le test d'appartenance renvoie vrai alors que l'élément est absent, c'est un faux positif. Les éléments ne peuvent pas être retirés de l'ensemble (bien que cela soit possible avec certaines variantes telles que les ). Le filtre de Bloom utilise un espace constant. C'est son principal intérêt.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (32)

Personnes associées (1)

Unités associées (4)

Concepts associés (7)

Cours associés (2)

Séances de cours associées (10)

Methodology for selecting measurement points that optimize information gain for model updating

Ian Smith, Numa Joy Bertola

Information collected through sensor measurements has the potential to improve knowledge of complex-system behavior, leading to better decisions related to system management. In this situation, and particularly when using digital twins, the quality of sens ...

2023

Indexing Protected Deep Face Templates by Frequent Binary Patterns

Sébastien Marcel, Hatef Otroshi Shahreza

In this work, we present a simple biometric indexing scheme which is binning and retrieving cancelable deep face templates based on frequent binary patterns. The simplicity of the proposed approach makes it applicable to unprotected as well as protected, i ...

IEEE2022

Applications such as large-scale sparse linear algebra and graph analytics are challenging to accelerate on FPGAs due to the short irregular memory accesses, resulting in low cache hit rates. Nonblocking caches reduce the bandwidth required by misses by re ...

ASSOC COMPUTING MACHINERY2022

Fonction de hachage parfait

droite|vignette|240x240px| Une fonction de hachage parfait pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. droite|vignette|240x240px| Une fonction de hachage parfait minimal pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. En informatique, une fonction de hachage parfait h pour un ensemble S est une fonction de hachage qui associe des éléments distincts de S à un ensemble de m entiers, sans collisions. En termes mathématiques, c'est une fonction injective.

Cuckoo hashing

Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches in a variation of the behavior referred to as brood parasitism; analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location in the table.

Self-balancing binary search tree

In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".

MATH-115(a): Advanced linear algebra II

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux de ce sujet.

CS-322: Introduction to database systems

This course provides a deep understanding of the concepts behind data management systems. It covers fundamental data management topics such as system architecture, data models, query processing and op

Couvre les matrices définies positives et leurs propriétés, en se concentrant sur la positivité stricte des mineurs principaux.

Couvre les matrices symétriques, les valeurs propres et le processus de diagonalisation pour les applications de théorèmes spectraux.

Explore le théorème spectral, en mettant l'accent sur le critère Min-Max pour les matrices symétriques et les propriétés des matrices définies positives.