Algorithms for Big Data: Distances (v1.0.4)

This package contains algorithms for computing distances between data points. It is a thin Python wrapper around the distances crate, in Rust. It provides drop-in replacements for the distance functions in scipy.spatial.distance.

Supported Distance Functions

Installation

pip install abd-distances

Usage

import math

import numpy
import abd_distances.simd as distance

a = numpy.array([i for i in range(10_000)], dtype=numpy.float32)
b = a + 1.0

dist = distance.euclidean(a, b)

assert math.fabs(dist - 100.0) < 1e-6

print(dist)
# 100.0

Vector Distances

• Bray-Curtis: abd_distances.vector.braycurtis
• Canberra: abd_distances.vector.canberra
• Chebyshev: abd_distances.vector.chebyshev
• Correlation
• Cosine: abd_distances.vector.cosine
• Euclidean: abd_distances.vector.euclidean
• Jensen-Shannon
• Mahalanobis
• Manhattan: abd_distances.vector.manhattan and abd_distances.vector.cityblock
• Minkowski: abd_distances.vector.minkowski
• Standardized Euclidean
• Squared Euclidean: abd_distances.vector.sqeuclidean
• Pairwise Distances: abd_distances.vector.cdist and abd_distances.vector.pdist
• ...

Boolean Distances

• Dice
• Hamming
• Jaccard
• Kulczynski 1D
• Rogers-Tanimoto
• Russell-Rao
• Sokal-Michener
• Sokal-Sneath
• Yule
• ...

SIMD-Accelerated Vector Distances

• Euclidean: abd_distances.simd.euclidean
• Squared Euclidean: abd_distances.simd.sqeuclidean
• Cosine: abd_distances.simd.cosine
• Pairwise Distances: abd_distances.simd.cdist and abd_distances.simd.pdist
• ...

String Distances

• Hamming: abd_distances.strings.hamming
• Levenshtein: abd_distances.strings.levenshtein
• Needleman-Wunsch: abd_distances.strings.needleman_wunsch
• Smith-Waterman
• Pairwise Distances
• ...

Benchmarks

SIMD-Accelerated Vector Distance Benchmarks

These benchmarks were run on an Intel Core i7-11700KF CPU @ 4.900GHz, using a single thread. The OS was Arch Linux, with kernel version 6.7.4-arch1-1.

The "Min", "Max", and "Mean" columns show the minimum, maximum, and mean times (in seconds), respectively, taken to compute the pairwise distances using the functions from scipy.spatial.distance. The "Min (+)", "Max (+)", and "Mean (+)" columns show the speedup of the this package's functions over the scipy functions. All pairwise distances (cdist and pdist) were computed for 200x200 vectors of 500 dimensions, and the average time was taken over 100 runs. All individual distances were computed for 20x20 vectors of 500 dimensions, and the average time was taken over 100 runs.

Vector Distance Benchmarks (No SIMD)

These benchmarks were run on an Intel Core i7-11700KF CPU @ 4.900GHz, using a single thread. The OS was Arch Linux, with kernel version 6.7.4-arch1-1.

The "Min", "Max", and "Mean" columns show the minimum, maximum, and mean times (in seconds), respectively, taken to compute the pairwise distances using the functions from scipy.spatial.distance. The "Min (+)", "Max (+)", and "Mean (+)" columns show the speedup of the this package's functions over the scipy functions. All pairwise distances (cdist and pdist) were computed for 200x200 vectors of 500 dimensions, and the average time was taken over 100 runs. All individual distances were computed for 20x20 vectors of 500 dimensions, and the average time was taken over 100 runs.

These benchmarks were run using the richbench package.

String Distance Benchmarks

These benchmarks were run on an Intel Core i7-11700KF CPU @ 4.900GHz, using a single thread. The OS was Arch Linux, with kernel version 6.7.4-arch1-1.

All string distances were computed 100 times each, among different pairs of strings, and the average time was taken.

License

This package is licensed under the MIT license.