BloomFilterer

class BloomFilterer(mapped_triples: Tensor, error_rate: float = 0.001)

Bases: Filterer

A filterer for negative triples based on the Bloom filter.

Pure PyTorch, a proper module which can be moved to GPU, and support batch-wise computation.

See also

• https://github.com/hiway/python-bloom-filter/ - for calculation of sizes, and rough structure of code

• https://github.com/skeeto/hash-prospector#two-round-functions - for parts of the hash function

Initialize the Bloom filter based filterer.

Parameters:

• mapped_triples (Tensor) – The ID-based triples.

• error_rate (float) – The desired error rate.

Methods Summary

add(triples)	Add triples to the Bloom filter.
contains(batch)	Check whether a triple is contained.
num_bits(num[, error_rate])	Determine the required number of bits.
num_probes(num_elements, num_bits)	Determine the number of probes / hashing rounds.
probe(batch)	Iterate over indices from the probes.

Methods Documentation

add(triples: Tensor) → None

Add triples to the Bloom filter.

Parameters:

triples (Tensor)

Return type:

None

contains(batch: Tensor) → Tensor

Check whether a triple is contained.

Parameters:

batch (Tensor) – shape (batch_size, 3) The batch of triples.

Returns:

shape: (batch_size,) The result. False guarantees that the element was not contained in the indexed triples. True can be erroneous.

Return type:

Tensor

static num_bits(num: int, error_rate: float = 0.01) → int

Determine the required number of bits.

Parameters:

• num (int) – The number of elements the Bloom filter shall store.

• error_rate (float) – The desired error rate.

Returns:

The required number of bits.

Return type:

int

static num_probes(num_elements: int, num_bits: int)

Determine the number of probes / hashing rounds.

Parameters:

• num_elements (int) – The number of elements.

• num_bits (int) – The number of bits, i.e., the size of the Bloom filter.

Returns:

The number of hashing rounds.

probe(batch: Tensor) → Iterable[Tensor]

Iterate over indices from the probes.

Parameters:

batch (Tensor) – shape: (batch_size, 3) A batch of elements.

Yields:

Indices of the k-th round, shape: (batch_size,).

Return type:

Iterable[Tensor]