Struct MinHash

pub struct MinHash<Word, const PERMUTATIONS: usize> { /* private fields */ }

Implementations

impl<Word: Maximal, const PERMUTATIONS: usize> MinHash<Word, PERMUTATIONS>

pub fn new() -> Self

Create a new MinHash.

Examples

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::new();

impl<Word: Min + XorShift + Copy + Eq + Maximal + Zero, const PERMUTATIONS: usize> MinHash<Word, PERMUTATIONS>

where u64: Primitive<Word>,

pub fn is_empty(&self) -> bool

Returns whether the MinHash is empty.

Examples

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u8, 16>::new();

assert!(minhash.is_empty());
minhash.insert_with_siphashes13(42);
assert!(!minhash.is_empty());

pub fn is_full(&self) -> bool

Returns whether the MinHash is fully saturated.

Examples

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u8, 16>::new();

assert!(!minhash.is_full());

for i in 0..1024 {
   minhash.insert_with_siphashes13(i);
}

assert!(minhash.is_full());

impl<Word: Min + XorShift + Copy + Eq, const PERMUTATIONS: usize> MinHash<Word, PERMUTATIONS>

where Self: IterHashes<Word, PERMUTATIONS>, u64: Primitive<Word>,

pub fn may_contain_value_with_siphashes13<H: Hash>(&self, value: H) -> bool

Returns whether the MinHash may contain the provided value, using the SipHasher13.

Arguments

• value - The value to check.

Implementative details

The procedure estimates whether the provided value is contained in the current MinHash data structure by checking whether all of the words are smaller or equal to all of the hash values that are calculated using the provided value as seed.

Examples

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::new();

assert!(!minhash.may_contain_value_with_siphashes13(42));
minhash.insert_with_siphashes13(42);
assert!(minhash.may_contain_value_with_siphashes13(42));
minhash.insert_with_siphashes13(47);
assert!(minhash.may_contain_value_with_siphashes13(47));

pub fn insert_with_siphashes13<H: Hash>(&mut self, value: H)

Insert a value into the MinHash using the SipHasher13.

Arguments

• value - The value to insert.

Examples

In the following example we show how we can create a MinHash and insert a value in it.

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::new();

assert!(!minhash.may_contain_value_with_siphashes13(42));
minhash.insert_with_siphashes13(42);
assert!(minhash.may_contain_value_with_siphashes13(42));
minhash.insert_with_siphashes13(47);
assert!(minhash.may_contain_value_with_siphashes13(47));

pub fn may_contain_value_with_keyed_siphashes13<H: Hash>( &self, value: H, key0: u64, key1: u64, ) -> bool

Returns whether the MinHash may contain the provided value, using the keyed SipHasher13.

Arguments

• value - The value to check.
• key0 - The first key.
• key1 - The second key.

Implementative details

The procedure estimates whether the provided value is contained in the current MinHash data structure by checking whether all of the words are smaller or equal to all of the hash values that are calculated using the provided value as seed.

Examples

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::new();
let key0 = 0x0123456789ABCDEF;
let key1 = 0xFEDCBA9876543210;

assert!(!minhash.may_contain_value_with_keyed_siphashes13(42, key0, key1));
minhash.insert_with_keyed_siphashes13(42, key0, key1);
assert!(minhash.may_contain_value_with_keyed_siphashes13(42, key0, key1));
minhash.insert_with_keyed_siphashes13(47, key0, key1);
assert!(minhash.may_contain_value_with_keyed_siphashes13(47, key0, key1));

pub fn insert_with_keyed_siphashes13<H: Hash>( &mut self, value: H, key0: u64, key1: u64, )

Insert a value into the MinHash using the keyed SipHasher13.

Arguments

• value - The value to insert.
• key0 - The first key.
• key1 - The second key.

Examples

In the following example we show how we can create a MinHash and insert a value in it.

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::new();
let key0 = 0x0123456789ABCDEF;
let key1 = 0xFEDCBA9876543210;

assert!(!minhash.may_contain_value_with_keyed_siphashes13(42, key0, key1));
minhash.insert_with_keyed_siphashes13(42, key0, key1);
assert!(minhash.may_contain_value_with_keyed_siphashes13(42, key0, key1));
minhash.insert_with_keyed_siphashes13(47, key0, key1);
assert!(minhash.may_contain_value_with_keyed_siphashes13(47, key0, key1));

pub fn may_contain_value_with_fvn<H: Hash>(&self, value: H) -> bool

Returns whether the MinHash may contain the provided value, using the FVN.

Arguments

• value - The value to check.

Implementative details

The procedure estimates whether the provided value is contained in the current MinHash data structure by checking whether all of the words are smaller or equal to all of the hash values that are calculated using the provided value as seed.

Examples

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::new();

assert!(!minhash.may_contain_value_with_fvn(42));
minhash.insert_with_fvn(42);
assert!(minhash.may_contain_value_with_fvn(42));
minhash.insert_with_fvn(47);
assert!(minhash.may_contain_value_with_fvn(47));

pub fn insert_with_fvn<H: Hash>(&mut self, value: H)

Insert a value into the MinHash using the FVN.

Arguments

• value - The value to insert.

Examples

In the following example we show how we can create a MinHash and insert a value in it.

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::new();

assert!(!minhash.may_contain_value_with_fvn(42));
minhash.insert_with_fvn(42);
assert!(minhash.may_contain_value_with_fvn(42));
minhash.insert_with_fvn(47);
assert!(minhash.may_contain_value_with_fvn(47));

pub fn may_contain_value_with_keyed_fvn<H: Hash>( &self, value: H, key: u64, ) -> bool

Returns whether the MinHash may contain the provided value, using the keyed FVN.

Arguments

• value - The value to check.
• key - The first key.

Implementative details

The procedure estimates whether the provided value is contained in the current MinHash data structure by checking whether all of the words are smaller or equal to all of the hash values that are calculated using the provided value as seed.

Examples

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::new();
let key = 0x0123456789ABCDEF;

assert!(!minhash.may_contain_value_with_keyed_fvn(42, key));
minhash.insert_with_keyed_fvn(42, key);
assert!(minhash.may_contain_value_with_keyed_fvn(42, key));
minhash.insert_with_keyed_fvn(47, key);
assert!(minhash.may_contain_value_with_keyed_fvn(47, key));

pub fn insert_with_keyed_fvn<H: Hash>(&mut self, value: H, key: u64)

Insert a value into the MinHash using the keyed FVN.

Arguments

• value - The value to insert.
• key - The first key.

Examples

In the following example we show how we can create a MinHash and insert a value in it.

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::new();
let key = 0x0123456789ABCDEF;

assert!(!minhash.may_contain_value_with_keyed_fvn(42, key));
minhash.insert_with_keyed_fvn(42, key);
assert!(minhash.may_contain_value_with_keyed_fvn(42, key));
minhash.insert_with_keyed_fvn(47, key);
assert!(minhash.may_contain_value_with_keyed_fvn(47, key));

impl<Word, const PERMUTATIONS: usize> MinHash<Word, PERMUTATIONS>

pub fn iter(&self) -> impl Iterator<Item = &Word>

Iterate over the words.

pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut Word>

Iterate over the words mutably.

pub fn number_of_permutations(&self) -> usize

Returns the number of permutations.

Examples

use minhash_rs::prelude::*;

let minhash = MinHash::<u64, 128>::new();

assert_eq!(minhash.number_of_permutations(), 128);

pub fn memory(&self) -> usize

Returns memory required to store the MinHash in bits.

Examples

For a MinHash with 128 permutations and 64 bit words, the memory required is 128 * 64 * 8.

use minhash_rs::prelude::*;

let minhash = MinHash::<u64, 128>::new();

assert_eq!(minhash.memory(), 128 * 64);

For a MinHash with 128 permutations and 32 bit words, the memory required is 128 * 32 * 8.

use minhash_rs::prelude::*;

let minhash = MinHash::<u32, 128>::new();

assert_eq!(minhash.memory(), 128 * 32);

impl<Word: Eq, const PERMUTATIONS: usize> MinHash<Word, PERMUTATIONS>

pub fn estimate_jaccard_index(&self, other: &Self) -> f64

Calculate the similarity between two MinHashes.

Arguments

• other - The other MinHash to compare to.

Examples

use std::collections::HashSet;
use minhash_rs::prelude::*;

let first_set: HashSet<u64> = [1_u64, 2_u64, 3_u64, 4_u64, 5_u64, 6_u64, 7_u64, 8_u64].iter().copied().collect();
let second_set: HashSet<u64> = [5_u64, 6_u64, 7_u64, 8_u64, 9_u64, 10_u64, 11_u64, 12_u64].iter().copied().collect();

let mut first_minhash: MinHash<u64, 128> = first_set.iter().collect();
let mut second_minhash: MinHash<u64, 128> = second_set.iter().collect();

let approximation = first_minhash.estimate_jaccard_index(&second_minhash);
let ground_truth = first_set.intersection(&second_set).count() as f64 / first_set.union(&second_set).count() as f64;

assert!((approximation - ground_truth).abs() < 0.01, concat!(
    "We expected the approximation to be close to the ground truth, ",
   "but got an error of {} instead. The ground truth is {} and the approximation is {}."
   ), (approximation - ground_truth).abs(), ground_truth, approximation
);

Trait Implementations

impl<Word, const PERMUTATIONS: usize> AsMut<[Word]> for MinHash<Word, PERMUTATIONS>

fn as_mut(&mut self) -> &mut [Word]

Converts this type into a mutable reference of the (usually inferred) input type.

impl<Word, const PERMUTATIONS: usize> AsRef<[Word]> for MinHash<Word, PERMUTATIONS>

We also implement AsRef and AsMut for direct access on the MinHash words.

fn as_ref(&self) -> &[Word]

Converts this type into a shared reference of the (usually inferred) input type.

impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicU16, PERMUTATIONS> for MinHash<u16, PERMUTATIONS>

fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicU16>

where Self: 'a,

Iterate over the words.

fn fetch_insert_with_siphashes13<H: Hash>(&self, value: H, ordering: Ordering)

Insert a value into the MinHash atomically, with SipHasher13.

fn fetch_insert_with_keyed_siphashes13<H: Hash>( &self, value: H, key0: u64, key1: u64, ordering: Ordering, )

Insert a value into the MinHash atomically, with keyed SipHasher13.

impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicU32, PERMUTATIONS> for MinHash<u32, PERMUTATIONS>

fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicU32>

where Self: 'a,

Iterate over the words.

fn fetch_insert_with_siphashes13<H: Hash>(&self, value: H, ordering: Ordering)

Insert a value into the MinHash atomically, with SipHasher13.

fn fetch_insert_with_keyed_siphashes13<H: Hash>( &self, value: H, key0: u64, key1: u64, ordering: Ordering, )

Insert a value into the MinHash atomically, with keyed SipHasher13.

impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicU64, PERMUTATIONS> for MinHash<u64, PERMUTATIONS>

fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicU64>

where Self: 'a,

Iterate over the words.

fn fetch_insert_with_siphashes13<H: Hash>(&self, value: H, ordering: Ordering)

Insert a value into the MinHash atomically, with SipHasher13.

fn fetch_insert_with_keyed_siphashes13<H: Hash>( &self, value: H, key0: u64, key1: u64, ordering: Ordering, )

Insert a value into the MinHash atomically, with keyed SipHasher13.

impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicU8, PERMUTATIONS> for MinHash<u8, PERMUTATIONS>

fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicU8>

where Self: 'a,

Iterate over the words.

fn fetch_insert_with_siphashes13<H: Hash>(&self, value: H, ordering: Ordering)

Insert a value into the MinHash atomically, with SipHasher13.

fn fetch_insert_with_keyed_siphashes13<H: Hash>( &self, value: H, key0: u64, key1: u64, ordering: Ordering, )

Insert a value into the MinHash atomically, with keyed SipHasher13.

impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicUsize, PERMUTATIONS> for MinHash<usize, PERMUTATIONS>

fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicUsize>

where Self: 'a,

Iterate over the words.

fn fetch_insert_with_siphashes13<H: Hash>(&self, value: H, ordering: Ordering)

Insert a value into the MinHash atomically, with SipHasher13.

fn fetch_insert_with_keyed_siphashes13<H: Hash>( &self, value: H, key0: u64, key1: u64, ordering: Ordering, )

Insert a value into the MinHash atomically, with keyed SipHasher13.

impl<Word: Min + Clone + Eq, const PERMUTATATIONS: usize> BitAnd<&MinHash<Word, PERMUTATATIONS>> for MinHash<Word, PERMUTATATIONS>

type Output = MinHash<Word, PERMUTATATIONS>

The resulting type after applying the & operator.

fn bitand(self, rhs: &Self) -> Self::Output

Performs the & operation.

impl<Word: Min + Clone + Eq, const PERMUTATATIONS: usize> BitAnd for MinHash<Word, PERMUTATATIONS>

type Output = MinHash<Word, PERMUTATATIONS>

The resulting type after applying the & operator.

fn bitand(self, rhs: Self) -> Self::Output

Performs the & operation.

impl<Word: Min + Clone + Eq, const PERMUTATATIONS: usize> BitAndAssign<&MinHash<Word, PERMUTATATIONS>> for MinHash<Word, PERMUTATATIONS>

fn bitand_assign(&mut self, rhs: &Self)

Performs the &= operation.

impl<Word: Min + Clone + Eq, const PERMUTATATIONS: usize> BitAndAssign for MinHash<Word, PERMUTATATIONS>

fn bitand_assign(&mut self, rhs: Self)

Performs the &= operation.

impl<Word: Clone, const PERMUTATIONS: usize> Clone for MinHash<Word, PERMUTATIONS>

fn clone(&self) -> MinHash<Word, PERMUTATIONS>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Word: Debug, const PERMUTATIONS: usize> Debug for MinHash<Word, PERMUTATIONS>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Word: Maximal, const PERMUTATIONS: usize> Default for MinHash<Word, PERMUTATIONS>

fn default() -> Self

Create a new MinHash with the maximal value.

Examples

use minhash_rs::prelude::*;

let mut minhash = MinHash::<u64, 128>::default();

assert_eq!(minhash, MinHash::<u64, 128>::new());

impl<Word: Min + Clone + Eq + Maximal + XorShift, A: Hash, const PERMUTATATIONS: usize> FromIterator<A> for MinHash<Word, PERMUTATATIONS>

where u64: Primitive<Word>,

fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self

Creates a new MinHash and adds all elements from an iterator to it.

Examples

use minhash_rs::prelude::*;

let data = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
let minhash = MinHash::<u64, 128>::from_iter(data.clone());

for item in data {
    assert!(minhash.may_contain_value_with_siphashes13(item));
}

impl<Word: Hash, const PERMUTATIONS: usize> Hash for MinHash<Word, PERMUTATIONS>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<W: Maximal, const PERMUTATIONS: usize> Index<usize> for MinHash<W, PERMUTATIONS>

We also provide indexing for the MinHash.

type Output = W

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<W: Maximal, const PERMUTATIONS: usize> IndexMut<usize> for MinHash<W, PERMUTATIONS>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<Word: Min + XorShift + Copy + Eq, const PERMUTATIONS: usize> IterHashes<Word, PERMUTATIONS> for MinHash<Word, PERMUTATIONS>

where u64: Primitive<Word>,

fn iter_hashes_from_value<H: Hash, HS: Hasher>( value: H, hasher: HS, ) -> impl Iterator<Item = Word>

Iterate on the hashes from the provided value and hasher.

fn iter_siphashes13_from_value<H: Hash>(value: H) -> impl Iterator<Item = Word>

Iterate on the SipHasher13 hashes from the provided value.

fn iter_keyed_siphashes13_from_value<H: Hash>( value: H, key0: u64, key1: u64, ) -> impl Iterator<Item = Word>

Iterate on the keyed SipHasher13 hashes from the provided value.

fn iter_fvn_from_value<H: Hash>(value: H) -> impl Iterator<Item = Word>

Iterate on the FVN hashes from the provided value.

fn iter_keyed_fvn_from_value<H: Hash>( value: H, key: u64, ) -> impl Iterator<Item = Word>

Iterate on the keyed SipHasher13 hashes from the provided value.

impl<Word: PartialEq, const PERMUTATIONS: usize> PartialEq for MinHash<Word, PERMUTATIONS>

fn eq(&self, other: &MinHash<Word, PERMUTATIONS>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<Word: Copy, const PERMUTATIONS: usize> Copy for MinHash<Word, PERMUTATIONS>

impl<Word: Eq, const PERMUTATIONS: usize> Eq for MinHash<Word, PERMUTATIONS>

impl<Word, const PERMUTATIONS: usize> StructuralPartialEq for MinHash<Word, PERMUTATIONS>