C · Set Similarity

Set Similarity

#include <numkong/set.h> 8.0.0-rc.1 · b1f866ab

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

nk_hamming_u1_bestBinary Hamming distance computing the number of differing bits between two binary vectors.
set.h:138 ↗
nk_status_t nk_hamming_u1_best(
    nk_u1x8_t const *a,
    nk_u1x8_t const *b,
    nk_size_t n,
    nk_u32_t *result,
    nk_capability_t capabilities,
    nk_stream_t stream);

Backends

  • nk_hamming_u1serialneonsvehaswellicelakervvbbrvvv128powervsxloongsonasx

Parameters

ainThe first binary vector.
binThe second binary vector.
ninCounts dimensions, a multiple of the values per byte.
resultoutThe output distance value.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Notes

  • The output distance value is non-negative.
  • The output distance value is zero if and only if the two vectors are identical.

Statuses

nk_jaccard_u1_bestBinary Jaccard distance computing the ratio of differing bits to the union of bits.
set.h:158 ↗
nk_status_t nk_jaccard_u1_best(
    nk_u1x8_t const *a,
    nk_u1x8_t const *b,
    nk_size_t n,
    nk_f32_t *result,
    nk_capability_t capabilities,
    nk_stream_t stream);

Backends

  • nk_jaccard_u1serialneonsvehaswellicelakervvbbrvvv128powervsxloongsonasx

Parameters

ainThe first binary vector.
binThe second binary vector.
ninCounts dimensions, a multiple of the values per byte.
resultoutThe output distance value.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Notes

  • The output distance value is non-negative.
  • The output distance value is zero if and only if the two vectors are identical.

Statuses

nk_jaccard_u32_bestIntegral Jaccard distance computing the ratio of differing bits to the union of bits.
set.h:178 ↗
nk_status_t nk_jaccard_u32_best(
    nk_u32_t const *a,
    nk_u32_t const *b,
    nk_size_t n,
    nk_f32_t *result,
    nk_capability_t capabilities,
    nk_stream_t stream);

Backends

  • nk_jaccard_u32serialneonsvehaswellicelakervvv128

Parameters

ainThe first binary vector.
binThe second binary vector.
ninThe number of 32-bit scalars in the vectors.
resultoutThe output distance value.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Notes

  • The output distance value is non-negative.
  • The output distance value is zero if and only if the two vectors are identical.

Statuses

nk_hamming_u8_bestByte-level Hamming distance computing the number of differing bytes between two vectors.
set.h:198 ↗
nk_status_t nk_hamming_u8_best(
    nk_u8_t const *a,
    nk_u8_t const *b,
    nk_size_t n,
    nk_u32_t *result,
    nk_capability_t capabilities,
    nk_stream_t stream);

Backends

  • nk_hamming_u8serialneonsvehaswellicelakervvv128powervsxloongsonasx

Parameters

ainThe first byte vector.
binThe second byte vector.
ninThe number of bytes in the vectors.
resultoutThe output distance value.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Notes

  • The output distance value is non-negative.
  • The output distance value is zero if and only if the two vectors are identical.

Statuses

nk_jaccard_u16_bestIntegral Jaccard distance for 16-bit unsigned integer vectors.
set.h:218 ↗
nk_status_t nk_jaccard_u16_best(
    nk_u16_t const *a,
    nk_u16_t const *b,
    nk_size_t n,
    nk_f32_t *result,
    nk_capability_t capabilities,
    nk_stream_t stream);

Backends

  • nk_jaccard_u16serialneonsvehaswellicelakervvv128

Parameters

ainThe first vector.
binThe second vector.
ninThe number of 16-bit scalars in the vectors.
resultoutThe output distance value.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Notes

  • The output distance value is non-negative.
  • The output distance value is zero if and only if the two vectors are identical.

Statuses

nk_hamming_output_dtypeReturns the output dtype for Hamming distance.
set.h:379 ↗
nk_dtype_t nk_hamming_output_dtype(nk_dtype_t dtype);
nk_jaccard_output_dtypeReturns the output dtype for Jaccard distance.
set.h:388 ↗
nk_dtype_t nk_jaccard_output_dtype(nk_dtype_t dtype);
nk_set_find_kernelFinds the set distance kernel of kind for dtype, from the best of capabilities.
set.h:409 ↗
nk_status_t nk_set_find_kernel(
    nk_kernel_kind_t kind,
    nk_dtype_t dtype,
    nk_capability_t capabilities,
    nk_kernel_punned_t *kernel,
    nk_capability_t *capability);

Parameters

kindinThe verb whose kernel to find.
dtypeinThe input type the kernel reads.
capabilitiesinThe mask to pick the best capability from.
kerneloutThe kernel, or null when none of capabilities has it.
capabilityoutThe capability the kernel belongs to, or zero.

Statuses