Set Similarity | NumKong for C++

Packed-binary metrics operate on packed words, not on byte-wise booleans. That is why u1x8_t exists as a storage type instead of pretending that bool[8] is the right primitive.

nk_u1x8_t a[128], b[128];
nk_u32_t hamming = 0;
nk_f32_t jaccard = 0;
nk_hamming_u1_best(a, b, 128 * 8, &hamming, capabilities, NULL);
nk_jaccard_u1_best(a, b, 128 * 8, &jaccard, capabilities, NULL);

nk_jaccard_u32_best is a dense word-wise kernel rather than a sorted-set operation. It walks two arrays of n 32-bit words position by position and returns 1 - matches / n.

nk_u32_t a[] = {1, 3, 5, 7, 9}, b[] = {1, 3, 5, 8, 10};
nk_f32_t jaccard_words = 0;
nk_jaccard_u32_best(a, b, 5, &jaccard_words, capabilities, NULL); // 1 - matches / n
assert(jaccard_words > 0.0f && jaccard_words < 1.0f && "3 of 5 words match");

Sorted arrays of integer identifiers are handled by the sparse kernels instead, described below.

API

Functions

hammingHamming distance: Σ(aᵢ ⊕ bᵢ).

set.hpp:32 ↗

template <numeric_dtype in_type_, numeric_dtype result_type_ = typename in_type_::hamming_result_t>
status_t hamming(
    in_type_ const *a,
    in_type_ const *b,
    std::size_t d,
    result_type_ *r,
    nk_capability_t capabilities = default_capabilities(),
    nk_stream_t stream = nullptr) noexcept;

template <numeric_dtype in_type_, numeric_dtype result_type_ = typename in_type_::hamming_result_t, vector_of<in_type_> a_type_, vector_of<in_type_> b_type_>
expected<result_type_> hamming(
    a_type_ const & a,
    b_type_ const & b,
    nk_capability_t capabilities = default_capabilities()) noexcept;

Hamming distance between two bit runs of equal dimensions; unexpected_dimensions_k when they differ or either run is strided or ends mid-value.

Parameters

`a`	in	First input vector
`b`	in	Second input vector
`d`	in	Counts dimensions, a multiple of the values per byte.
`r`	out	Pointer to output count
`capabilities`	in	Capabilities to pick from, or zero for the C++ template
`stream`	in	Null on the CPU, or the stream of the device `capabilities` describes

jaccardJaccard distance: 1 − |A ∩ B| / |A ∪ B|.

set.hpp:66 ↗

template <numeric_dtype in_type_, numeric_dtype result_type_ = typename in_type_::jaccard_result_t>
status_t jaccard(
    in_type_ const *a,
    in_type_ const *b,
    std::size_t d,
    result_type_ *r,
    nk_capability_t capabilities = default_capabilities(),
    nk_stream_t stream = nullptr) noexcept;

template <numeric_dtype in_type_, numeric_dtype result_type_ = typename in_type_::jaccard_result_t, vector_of<in_type_> a_type_, vector_of<in_type_> b_type_>
expected<result_type_> jaccard(
    a_type_ const & a,
    b_type_ const & b,
    nk_capability_t capabilities = default_capabilities()) noexcept;

Jaccard distance between two bit runs, failing like the concept hamming.

For u1x8_t bit vectors, uses popcount(AND) / popcount(OR). For u16_t/u32_t element vectors, uses count of matching elements / total.

Parameters

`a`	in	First input vector
`b`	in	Second input vector
`d`	in	Counts dimensions, a multiple of the values per byte.
`r`	out	Pointer to output distance
`capabilities`	in	Capabilities to pick from, or zero for the C++ template
`stream`	in	Null on the CPU, or the stream of the device `capabilities` describes