BitFunnel

 ( Data Management ) 

In contrast, BitFunnel represents each searchable item through a signature. A signature is a sequence of bits which describe a Bloom filter of the searchable terms in a given searchable item. The bloom filter is constructed through hashing through several bit positions.

$$\backslash overrightarrow\{S\_D\}=\backslash bigcup\_\{t\; \backslash in\; D\}\; \backslash overrightarrow\{S\_t\}$$

Similarly, a query for a document (Q) can be defined as a union:

$$\backslash overrightarrow\{S\_Q\}=\backslash bigcup\_\{t\; \backslash in\; Q\}\; \backslash overrightarrow\{S\_t\}$$

Additionally, a document D is a member of the set M' when the following condition is satisfied:

$$\backslash overrightarrow\{S\_Q\}\; \backslash cap\; \backslash overrightarrow\{S\_D\}\; =\; \backslash overrightarrow\{S\_Q\}$$

This knowledge is then combined to produce a formula where M' is identified by documents which match the query signature:

$$M\text{'}=\; \backslash left\backslash \{\; D\; \backslash in\; C\; \backslash mid\; \backslash overrightarrow\{S\_Q\}\; \backslash cap\; \backslash overrightarrow\{S\_D\}\; =\; \backslash overrightarrow\{S\_Q\}\backslash right\backslash \}$$

These steps and their proofs are discussed in the 2017 paper.