Distance Metrics
Relevant source files
The following files were used as context for generating this wiki page:
Distance metrics are fundamental components of the EdgeVec vector database, serving as the mathematical foundation for similarity search and nearest neighbor retrieval. These metrics define how "close" two vectors are in a multi-dimensional space, which directly influences the ranking of search results. EdgeVec implements these metrics using high-performance Rust code optimized for both native execution and WebAssembly (WASM) environments.
The project prioritizes performance through SIMD (Single Instruction, Multiple Data) acceleration, significantly increasing throughput for vector operations. These metrics are integrated into the core indexing layers, such as HNSW, to facilitate O(log n) search complexity.
Sources: README.md:16-25, wasm/examples/simd_benchmark.html:150-165
Metric Architecture and Traits
EdgeVec uses a trait-based architecture to provide a unified interface for different distance calculations. The Metric trait defines the standard behavior required for any distance measure used within the index.
The Metric Trait
The core abstraction is defined in src/metric/mod.rs. It ensures that all distance metrics provide a consistent way to calculate scores between vectors.
The diagram above represents the relationship between the base metric trait and its specific floating-point implementations. Note that Hamming distance operates on quantized byte arrays.
Sources: src/metric/mod.rs, src/metric/dot.rs:1-10, src/metric/l2.rs:1-10
Supported Metrics
EdgeVec provides several specialized metrics tailored for different embedding types and performance requirements.
Euclidean (L2) Distance
L2 distance measures the straight-line distance between two points in Euclidean space. It is commonly used for embeddings where the magnitude of the vector is significant.
- Implementation: Calculates the square root of the sum of squared differences between corresponding components.
- Optimization: EdgeVec often uses squared L2 distance to avoid expensive square root operations during ranking.
Sources: src/metric/l2.rs, README.md:110-115
Dot Product
Dot product measures the cosine of the angle between two vectors multiplied by their magnitudes. It is the default metric for many modern transformer-based embeddings.
- Implementation: Sum of the products of the corresponding entries of the two sequences of numbers.
- Usage: Ideal for normalized vectors where it effectively calculates Cosine Similarity.
Sources: src/metric/dot.rs, README.md:110-115
Hamming Distance
Hamming distance is used primarily with Binary Quantization (BQ). It counts the number of positions at which the corresponding bits are different.
- Implementation: Uses the
XORoperation followed by a population count (popcount). - Performance: Extremely fast, capable of achieving throughput up to 40 GiB/s due to bitwise optimizations and SIMD.
Sources: src/metric/hamming.rs, README.md:125-130
Performance and SIMD Optimization
A key feature of EdgeVec is the use of SIMD instructions to accelerate distance calculations. This is particularly effective for high-dimensional vectors (e.g., 768D or 1536D).
Throughput Comparison
| Metric | Dimension | Throughput (Native) |
|---|---|---|
| Dot Product | 768 | 2.1 Gelem/s |
| L2 Distance | 768 | 2.1 Gelem/s |
| Hamming | 768-bit pair | 40 GiB/s |
Sources: README.md:110-120, wasm/examples/simd_benchmark.html:450-465
SIMD Data Flow
When calculating distances, SIMD allows the processor to load multiple values into 128-bit registers and perform operations in parallel.
This diagram illustrates the SIMD pipeline for a Dot Product calculation where four components are processed simultaneously per cycle.
Sources: wasm/examples/simd_benchmark.html:480-500, README.md:105-110
Usage in WebAssembly
EdgeVec detects SIMD support at runtime within the browser. If SIMD128 is available, the engine uses vectorized kernels; otherwise, it falls back to scalar implementations.
| Environment | Support | Performance |
|---|---|---|
| Chrome/Firefox/Edge | SIMD128 | Full Speed (2x+ boost) |
| Safari (macOS) | SIMD128 | Full Speed |
| iOS Safari | Scalar | Fallback (~2x slower) |
Sources: README.md:135-145, wasm/examples/simd_benchmark.html:580-600
Summary
Distance metrics in EdgeVec are engineered for high-throughput similarity search. By utilizing a modular trait system, the database supports standard Euclidean and Dot Product measures for floating-point vectors, alongside an ultra-fast Hamming distance implementation for binary-quantized data. The integration of SIMD ensures that these calculations do not become a bottleneck, even when searching through hundreds of thousands of high-dimensional vectors in a browser-based environment.