Crate ruvector_hyperbolic_hnsw

Expand description

Hyperbolic Embeddings with HNSW Integration for RuVector

This crate provides hyperbolic (Poincaré ball) embeddings integrated with HNSW (Hierarchical Navigable Small World) graphs for hierarchy-aware vector search.

§Overview

Hierarchies compress naturally in hyperbolic space. Taxonomies, catalogs, ICD trees, product facets, org charts, and long-tail tags all fit better than in Euclidean space, which means higher recall on deep leaves without blowing up memory or latency.

§Key Features

Poincaré Ball Model: Store vectors in the Poincaré ball with proper geometric operations (Möbius addition, exp/log maps)
Tangent Space Pruning: Prune HNSW candidates with cheap Euclidean distance in tangent space before exact hyperbolic ranking
Per-Shard Curvature: Different parts of the hierarchy can have different optimal curvatures
Dual-Space Index: Keep a synchronized Euclidean index for fallback and mutual ranking fusion

§Quick Start

use ruvector_hyperbolic_hnsw::{HyperbolicHnsw, HyperbolicHnswConfig};

// Create index with default settings
let mut index = HyperbolicHnsw::default_config();

// Insert vectors (automatically projected to Poincaré ball)
index.insert(vec![0.1, 0.2, 0.3]).unwrap();
index.insert(vec![-0.1, 0.15, 0.25]).unwrap();
index.insert(vec![0.2, -0.1, 0.1]).unwrap();

// Search for nearest neighbors
let results = index.search(&[0.15, 0.1, 0.2], 2).unwrap();
for r in results {
    println!("ID: {}, Distance: {:.4}", r.id, r.distance);
}

§HNSW Speed Trick

The core optimization is:

Precompute u = log_c(x) at a shard centroid c
During neighbor selection, use Euclidean ||u_q - u_p|| to prune
Run exact Poincaré distance only on top N candidates before final ranking

use ruvector_hyperbolic_hnsw::{HyperbolicHnsw, HyperbolicHnswConfig};

let mut config = HyperbolicHnswConfig::default();
config.use_tangent_pruning = true;
config.prune_factor = 10; // Consider 10x candidates in tangent space

let mut index = HyperbolicHnsw::new(config);
// ... insert vectors ...

// Build tangent cache for pruning optimization
index.build_tangent_cache().unwrap();

// Search with pruning
let results = index.search_with_pruning(&[0.1, 0.15], 5).unwrap();

§Sharded Index with Per-Shard Curvature

use ruvector_hyperbolic_hnsw::{ShardedHyperbolicHnsw, ShardStrategy};

let mut manager = ShardedHyperbolicHnsw::new(1.0);

// Insert with hierarchy depth information
manager.insert(vec![0.1, 0.2], Some(0)).unwrap(); // Root level
manager.insert(vec![0.3, 0.1], Some(3)).unwrap(); // Deeper level

// Update curvature for specific shard
manager.update_curvature("radius_1", 0.5).unwrap();

// Search across all shards
let results = manager.search(&[0.2, 0.15], 5).unwrap();

§Mathematical Operations

The poincare module provides low-level hyperbolic geometry operations:

use ruvector_hyperbolic_hnsw::poincare::{
    mobius_add, exp_map, log_map, poincare_distance, project_to_ball
};

let x = vec![0.3, 0.2];
let y = vec![-0.1, 0.4];
let c = 1.0; // Curvature

// Möbius addition (hyperbolic vector addition)
let z = mobius_add(&x, &y, c);

// Geodesic distance in hyperbolic space
let d = poincare_distance(&x, &y, c);

// Map to tangent space at x
let v = log_map(&y, &x, c);

// Map back to manifold
let y_recovered = exp_map(&v, &x, c);

§Numerical Stability

All operations include numerical safeguards:

Norm clamping with eps = 1e-5
Projection after every update
Stable acosh and log1p implementations

§Feature Flags

simd: Enable SIMD acceleration (default)
parallel: Enable parallel processing with rayon (default)
wasm: Enable WebAssembly compatibility

Re-exports§

pub use error::HyperbolicError;
pub use error::HyperbolicResult;
pub use hnsw::DistanceMetric;
pub use hnsw::DualSpaceIndex;
pub use hnsw::HnswNode;
pub use hnsw::HyperbolicHnsw;
pub use hnsw::HyperbolicHnswConfig;
pub use hnsw::SearchResult;
pub use poincare::conformal_factor;
pub use poincare::conformal_factor_from_norm_sq;
pub use poincare::dot;
pub use poincare::exp_map;
pub use poincare::frechet_mean;
pub use poincare::fused_norms;
pub use poincare::hyperbolic_midpoint;
pub use poincare::log_map;
pub use poincare::log_map_at_centroid;
pub use poincare::mobius_add;
pub use poincare::mobius_add_inplace;
pub use poincare::mobius_scalar_mult;
pub use poincare::norm;
pub use poincare::norm_squared;
pub use poincare::parallel_transport;
pub use poincare::poincare_distance;
pub use poincare::poincare_distance_batch;
pub use poincare::poincare_distance_from_norms;
pub use poincare::poincare_distance_squared;
pub use poincare::project_to_ball;
pub use poincare::project_to_ball_inplace;
pub use poincare::PoincareConfig;
pub use poincare::DEFAULT_CURVATURE;
pub use poincare::EPS;
pub use shard::CurvatureRegistry;
pub use shard::HierarchyMetrics;
pub use shard::HyperbolicShard;
pub use shard::ShardCurvature;
pub use shard::ShardStrategy;
pub use shard::ShardedHyperbolicHnsw;
pub use tangent::tangent_micro_update;
pub use tangent::PrunedCandidate;
pub use tangent::TangentCache;
pub use tangent::TangentPruner;

Modules§

error: Error types for hyperbolic HNSW operations
hnsw: HNSW Adapter with Hyperbolic Distance Support
poincare: Poincaré Ball Model Operations for Hyperbolic Geometry
prelude: Prelude for common imports
shard: Shard Management with Curvature Registry
tangent: Tangent Space Operations for HNSW Pruning Optimization

Constants§

VERSION: Library version