performance(mincut): replace O(m) edge scans in LocalKCut::check_cut with indexed lookup
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 4.5k
- Forks
- 603
- Avg merge
- 23h 32m
- Merged PRs (30d)
- 59
Description
Confirmed defect
LocalKCut::check_cut currently handles each boundary adjacency by calling self.graph.edges() and linearly searching the returned full-edge Vec by edge_id:
self.graph.edges().iter().find(|e| e.id == edge_id)
This is reachable on the default branch in crates/ruvector-mincut/src/localkcut/mod.rs. DynamicGraph already maintains edge_index and exposes get_edge(u, v), an endpoint-indexed lookup.
Evidence
PR #941 isolated the effect while testing min-cut-guided HNSW deletion repair:
- individual
find_cutcalls: 24.8–158.0 seconds at HNSW construction densitym0=32 - completed three-deletion run: 318,024.78 ms for
LocalCutGuidedversus 0.78 ms forEagerRepair - the same order of magnitude appeared in three independent attempts
The broader HNSW repair hypothesis remains rejected because small-world topology also violates the local algorithm's bounded-degree assumptions. This issue concerns only the independent full-edge scan defect.
Minimal candidate
Use the existing endpoint lookup for each boundary adjacency, preserving edge weight and cut-edge semantics:
if let Some(edge) = self.graph.get_edge(v, neighbor) {
cut_edges.push((v, neighbor));
cut_value += edge.weight;
}
Acceptance criteria
- Existing
ruvector-mincutcorrectness tests remain green. - Add a regression that verifies identical cut membership and weight before/after the lookup change on weighted undirected graphs.
- Add a fixed seeded dense-graph benchmark comparing the current scan implementation with the indexed implementation.
- Indexed lookup is at least 100× faster on the recorded dense fixture without changing the returned
LocalCutResult. cargo test -p ruvector-mincut,cargo clippy -p ruvector-mincut --all-targets -- -D warnings, and the relevant workspace CI shard pass.- Do not revive or claim acceptance of the rejected min-cut-guided HNSW repair design without a separate preregistered experiment.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in crates/ruvector-mincut/src/localkcut/mod.rs, focusing on LocalKCut::check_cut and DynamicGraph's existing get_edge lookup. Run cargo test -p ruvector-mincut and inspect the correctness tests before adding the weighted undirected regression and fixed-seed dense-graph benchmark. Done means unchanged LocalCutResult values, at least a 100× benchmark improvement, and passing the specified clippy and workspace CI checks.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 68/100