rUv
|
2fd0e74312
|
feat: add ruvector-sparsifier — dynamic spectral graph sparsification
* feat: add ruvector-sparsifier crate — dynamic spectral graph sparsification
Implements AdaptiveGeoSpar, a dynamic spectral sparsifier that maintains
a compressed shadow graph preserving Laplacian energy within (1±ε).
Core crate (ruvector-sparsifier):
- SparseGraph with dynamic edge operations and Laplacian QF
- Backbone spanning forest via union-find for connectivity
- Random walk effective resistance estimation for importance scoring
- Spectral sampling proportional to weight × importance × log(n)/ε²
- SpectralAuditor with quadratic form, cut, and conductance probes
- Pluggable traits: Sparsifier, ImportanceScorer, BackboneStrategy
- 49 tests (31 unit + 17 integration + 1 doc-test), all passing
- Benchmarks: build 161µs, insert 81µs, audit 39µs (n=100)
WASM crate (ruvector-sparsifier-wasm):
- Full wasm-bindgen bindings via WasmSparsifier and WasmSparseGraph
- JSON-based API for browser/edge deployment
- Compiles cleanly on native target
Research (docs/research/spectral-sparsification/):
- 00: Executive summary and impact projections
- 01: SOTA survey (ADKKP 2016 → STACS 2026)
- 02: Rust crate design and API
- 03: RuVector integration architecture (4-tier control plane)
- 04: Companion systems (conformal drift, attributed ANN)
https://claude.ai/code/session_01A6YKtTrSPeV36Xamz9hRCb
* perf: ultra optimizations across core distance, SIMD, and sparsifier hot paths
Core distance.rs:
- Manhattan distance now delegates to SIMD (was pure scalar)
- Cosine fallback uses single-pass computation (was 3 separate passes)
- Euclidean fallback uses 4x loop unrolling for better ILP
SIMD intrinsics:
- Add AVX2 manhattan distance (was only AVX-512 or scalar fallback)
- 2x loop unrolling with dual accumulators for AVX2 manhattan
- Sign-bit mask absolute value for branchless abs diff
Sparsifier (O(m) -> O(1) per insert):
- Cache total importance to avoid iterating ALL edges per insert
- Parallel edge scoring via rayon for graphs >100 edges
- Pre-sized HashMap adjacency lists (4 neighbors avg)
- Inline annotations on hot-path graph query methods
https://claude.ai/code/session_01A6YKtTrSPeV36Xamz9hRCb
* fix: resolve clippy warnings in ruvector-sparsifier
- Replace map_or(false, ...) with is_some_and(...) in graph.rs
- Derive Default instead of manual impl for LocalImportanceScorer
- Fix inner/outer attribute conflict on prelude module
Co-Authored-By: claude-flow <ruv@ruv.net>
---------
Co-authored-by: Claude <noreply@anthropic.com>
|
2026-03-20 10:37:39 -04:00 |
|