BitFunnel

El artículo de BitFunnel describe el "problema de coincidencia", que surge cuando un algoritmo debe identificar documentos mediante el uso de palabras clave. El objetivo es identificar un conjunto de coincidencias a partir de un corpus para buscar y una consulta de términos clave con los que comparar. Este problema se suele resolver mediante índices invertidos , donde cada elemento de búsqueda se mantiene con un mapa de palabras clave. ^{[ 3 ]}

En cambio, BitFunnel representa cada elemento de búsqueda mediante una firma. Una firma es una secuencia de bits que describe un filtro Bloom de los términos de búsqueda en un elemento determinado. El filtro Bloom se construye mediante el hash de varias posiciones de bits. ^{[ 3 ]}

La firma de un documento (D) puede describirse como la disyunción lógica de sus firmas de términos:

$${\displaystyle {\overrightarrow {S_{D}}}=\bigcup _{t\in D}{\overrightarrow {S_{t}}}}$$

De manera similar, una consulta para un documento (Q) puede definirse como una unión:

$${\displaystyle {\overrightarrow {S_{Q}}}=\bigcup _{t\in Q}{\overrightarrow {S_{t}}}}$$

Además, un documento D es miembro del conjunto M' cuando se cumple la siguiente condición:

$${\displaystyle {\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}}$$

Este conocimiento se combina luego para producir una fórmula donde M' se identifica mediante documentos que coinciden con la firma de la consulta:

$${\displaystyle M'=\left\{D\in C\mid {\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}\right\}}$$

Estos pasos y sus demostraciones se analizan en el artículo de 2017. ^{[ 3 ]}

Este algoritmo se describe en el artículo de 2017. ^{[ 3 ]}$${\displaystyle {\begin{array}{l}M'=\emptyset \\{\texttt {foreach}}\ D\in C\ {\texttt {do}}\\\qquad {\texttt {if}}\ {\overrightarrow {S_{D}}}\cap {\overrightarrow {S_{Q}}}={\overrightarrow {S_{Q}}}\ {\texttt {then}}\\\qquad \qquad M'=M'\cup \{D\}\\\qquad {\texttt {endif}}\\{\texttt {endfor}}\end{array}}}$$