mirror of
https://github.com/ruvnet/RuVector.git
synced 2026-07-09 17:28:42 +00:00
afcaf07669
* feat(rvf): ANN search across COW branches (dual-graph merge) Stack on feat/queryable-cow-branches (PR #617). That PR added branch(), CowEngine, MembershipFilter, and parent_path — but the HNSW/ANN paths were disabled for COW children (fell back to O(N) exact scan of child's own slab only, missing parent vectors entirely). This commit adds sub-linear ANN across the full parent ∪ child-edits view: Design — dual-graph query + merge (LSM-ANN pattern): 1. Child arm : query child's own HNSW (exact scan when child < 1 024 vectors) 2. Parent arm : lazily open parent store read-only, cache in parent_store Mutex<Option<Box<RvfStore>>>; query parent's HNSW (built once, no rebuild per branch) 3. Over-fetch : k' = k × 4 from each arm to absorb tombstones / overrides 4. Merge : child distances override parent for same ID; IDs removed from membership_filter (tombstoned via child delete) are excluded; re-rank by distance; return top-k 5. Chained COW : parent.query() walks parent's own HNSW; lineage works transitively Key changes to rvf-runtime/src/store.rs: - Add parent_store: Mutex<Option<Box<RvfStore>>> field (all constructors) - Fix query_routed early-return: COW children with 0 child-side vectors must not bail before parent read-through - New cow_ann_eligible() guard - New query_via_index_cow() — the dual-graph merge (replaces O(N) fallback) - New cow_exact_parent_scan() — exact parent read-through for the exact path; makes query_exact the correct ground-truth for recall comparison - Update query_exact to call cow_exact_parent_scan for COW children - Update delete() to tombstone parent IDs from membership_filter so child-side deletion of inherited parent vectors is correctly reflected New integration tests (cow_ann_recall.rs, 4 tests): - cow_ann_recall_vs_exact : 1 200-vector base, branch, add/override/delete; ANN recall@10 vs exact ground truth — measured 1.0000 (>= 0.95 contract) - cow_ann_override_correctness: child override returns child distance, not parent's stale entry - cow_ann_tombstone_absent : tombstoned ID absent from ANN and exact results - cow_branch_size_independence: child file (162 bytes) stays << parent (163 803 bytes) after queries — no HNSW rebuild in child file Approximation: dual-graph merge is slightly approximate (sub-linear in parent size, not exact). Measured recall@10 = 1.00 at ef_search=300 on 1 200-vector L2/32-dim dataset with C=4 over-fetch. force_exact=true always provides ground truth via cow_exact_parent_scan. Cost: 2 HNSW queries (child + parent), flat in parent size. Parent HNSW built once on first COW query then cached. Child HNSW only when child has >= 1 024 vectors. RaBitQ-across-COW deferred (exact fallback used until then). Co-Authored-By: claude-flow <ruv@ruv.net> Claude-Session: https://claude.ai/code/session_019rVRYrRDKyxYK18kuVrDSf * fix(diskann): make search_returns_self_as_nearest non-flaky The test used max_degree=16 / beam=16 on a 128-node graph whose initial topology comes from thread_rng() (VamanaGraph::init_random_graph). With small M and a random graph, point 5 can end up outside the 16-candidate window reachable from the medoid in some seedings — causing an intermittent CI failure unrelated to the caller's changes. Fix: bump max_degree to 32 and build_beam to 64 (matching production defaults) so the graph is dense enough to guarantee connectivity on 128 nodes; use n = v.len() as the search beam so the test validates the "self is retrievable" property exhaustively rather than testing ANN efficiency (which is covered by other tests). Fixes pre-existing flaky failure observed in Tests (vector-index) CI job. Co-Authored-By: claude-flow <ruv@ruv.net> Claude-Session: https://claude.ai/code/session_019rVRYrRDKyxYK18kuVrDSf --------- Co-authored-by: ruvnet <ruvnet@gmail.com> |
||
|---|---|---|
| .. | ||
| src | ||
| Cargo.toml | ||