numkong

NumKong provides optimized implementations for Hamming and Jaccard distance measures, which are essential for locality-sensitive hashing, MinHash sketches, and binary feature matching.

Hamming Distance

Counts the number of positions where elements differ.

• Binary vectors (packed octets): Counts the popcount of the XOR result.
• Byte-level vectors: Counts the number of mismatched bytes.

Jaccard Distance

Measures the dissimilarity of two sets.

• Binary vectors: Calculated as $1 - \frac{|A \cap B|}{|A \cup B|}$ using bitwise AND/OR and popcount.
• Word-level vectors (MinHash signatures): Calculated as the fraction of non-matching elements: $1 - \frac{\sum [a_i = b_i]}{n}$.

import numpy as np

def hamming_bits(a: np.ndarray, b: np.ndarray) -> int:
    return np.unpackbits(np.bitwise_xor(a, b)).sum()

def jaccard_bits(a: np.ndarray, b: np.ndarray) -> float:
    intersection = np.unpackbits(np.bitwise_and(a, b)).sum()
    union = np.unpackbits(np.bitwise_or(a, b)).sum()
    return 1 - intersection / union if union else 0

def jaccard_words(a: np.ndarray, b: np.ndarray) -> float:
    return 1 - np.mean(a == b)

NumKong provides optimized horizontal reduction operations designed for high performance across various backends. These reductions focus on balancing latency, throughput, and numerical stability. Key features include:

• Input & Output Types: Support for various numeric types.
• Optimizations: Includes auto-vectorization, loop unrolling, and strided access across backends.
• Numerical Stability: Implements Kahan-Neumaier compensated summation to minimize rounding errors.
• Advanced Reductions:
  • Fused Moments: Calculates multiple moments in a single pass.
  • Integer Saturation: Handles sum-of-squares with integer saturation.
  • Recursive Blocking: Prevents counter overflow.
  • NaN-Aware Extrema Tracking: Robustly tracks minimum and maximum values even in the presence of NaNs.
• Performance: Optimized for modern hardware, including Intel Sapphire Rapids.

NumKong provides high-performance primitives for sparse vector operations, specifically designed for inverted-index search, sparse feature matching, and graph intersection queries. The library implements two primary operations:

1. Set Intersection: Counts the number of common elements between two sorted arrays of unique indices.
2. Sparse Dot Product: Calculates the sum of products of weights at matching indices between two sparse vectors.

The design separates index streams from weight streams, allowing these primitives to be composed into batched sparse operations and future sparse GEMM (General Matrix Multiply) workloads.

import numpy as np

# Conceptual representation of NumKong's logic
def intersect(a_indices: np.ndarray, b_indices: np.ndarray) -> int:
    return len(np.intersect1d(a_indices, b_indices))

def sparse_dot(a_indices: np.ndarray, a_weights: np.ndarray, 
               b_indices: np.ndarray, b_weights: np.ndarray) -> float:
    common = np.intersect1d(a_indices, b_indices, return_indices=True)
    return np.dot(a_weights[common[1]], b_weights[common[2]])

NumKong provides optimized implementations for distance functions in curved metric spaces, specifically for Gaussian process inference, metric learning, and statistical distance measures.

Supported operations include:

• Bilinear forms: Computes $a^T C b$ for real vectors or $a^H C b$ (Hermitian inner products) for complex vectors using a metric tensor $C$.
• Mahalanobis distance: Generalizes Euclidean distance to account for correlations between dimensions using the formula $\sqrt{(a - b)^T C (a - b)}$.

import numpy as np

# Pseudocode representation of NumKong operations
def bilinear(a: np.ndarray, b: np.ndarray, C: np.ndarray) -> float:
    return a @ C @ b

def mahalanobis(a: np.ndarray, b: np.ndarray, C: np.ndarray) -> float:
    diff = a - b
    return np.sqrt(diff @ C @ diff)

def bilinear_complex(a: np.ndarray, b: np.ndarray, C: np.ndarray) -> complex:
    return np.conj(a) @ C @ b

NumKong provides two primary methods for computing geodesic distances between points on Earth's surface using arrays of latitude/longitude pairs in radians:

1. Haversine: Computes the great-circle distance on a perfect sphere. Use this for faster, less precise calculations.
2. Vincenty: Solves the inverse geodesic problem on the WGS-84 oblate spheroid. Use this for high-precision requirements (convergence threshold of $10^{-12}$ radians, approximately 6 micrometers accuracy).

Input Requirements:

• Coordinates must be in radians.
• Input/Output types support f32 (32-bit single precision) and f64 (64-bit double precision).
• Output distances are returned in meters.

import numpy as np

def haversine(lat1, lon1, lat2, lon2, R=6371000):
    dlat = lat2 - lat1
    dlon = lon2 - lon1
    a = np.sin(dlat / 2) ** 2 + np.cos(lat1) * np.cos(lat2) * np.sin(dlon / 2) ** 2
    return 2 * R * np.arcsin(np.sqrt(a))

The Go package is a cGo wrapper. When using it, observe the following rules regarding memory and safety:

Memory Management:

• Ownership: The slice backing arrays remain owned by Go. NumKong does not wrap slices in extra heap-owning tensor objects.
• Pinning: Go automatically pins slice backing arrays for the duration of each cGo call; no manual runtime.Pinner is required.
• Lifecycle: PackedMatrix and MaxSimPacked structs hold strong Go references to their []byte buffers, keeping them alive for GC as long as the struct is reachable.

Safety and Validation:

• Panics: Length mismatches and insufficient slice capacity will cause a panic across all functions.
• Validation: Constructors validate that input slices are large enough for the specified dimensions. Batch functions validate both input and output slice sizes.
• Empty Slices: Empty slices return zero for scalar outputs instead of crashing.
• Symmetric Matrices: Output matrices for symmetric operations must be exactly $n imes n$ in size.