# How the SIMILAR_TO Edge Uses MinHash LSH for Near-Clone Detection in codebase-memory-mcp

> Discover how codebase-memory-mcp uses SIMILAR_TO edge and MinHash LSH for efficient near-clone detection within codebases. Learn about the Jaccard similarity workflow.

- Repository: [Martin Vogel/codebase-memory-mcp](https://github.com/DeusData/codebase-memory-mcp)
- Tags: deep-dive
- Published: 2026-07-16

---

**The `SIMILAR_TO` edge is created by the pass-similarity pipeline stage that implements a MinHash + Locality-Sensitive Hashing (LSH) workflow to detect function pairs with Jaccard similarity ≥ 0.95.**

The `codebase-memory-mcp` repository provides a high-performance near-duplicate detection system that identifies structurally similar code across large repositories. By leveraging **MinHash LSH near-clone detection**, the system efficiently fingerprints abstract syntax trees (ASTs) and creates `SIMILAR_TO` edges in the graph database, enabling developers to track code clones and copy-paste patterns at scale.

## How MinHash Fingerprints Capture Code Structure

The detection process begins in [`src/simhash/minhash.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/simhash/minhash.c) where the `cbm_minhash_compute()` function transforms each function body into a compact signature. While walking the AST, the algorithm normalizes leaf tokens into categories (`I` for identifiers, `S` for strings, `N` for numbers, `T` for types) and generates trigrams from the token stream.

For each of **64** hash permutations (defined by `CBM_MINHASH_K`), the system computes xxHash values using different seeds and retains the minimum hash. This produces a 64-element MinHash signature that serves as an unbiased estimator of Jaccard similarity between code structures.

```c
/* Computing a fingerprint in src/simhash/minhash.c */
cbm_minhash_t fp;
bool ok = cbm_minhash_compute(func_body_node, source_text, language_id, &fp);
if (!ok) return false;

```

## Hex Encoding and Fingerprint Collection

Before storage, the 64 × 32-bit signature values are serialized into a 512-character hex string via `cbm_minhash_to_hex()`. This string is stored in the node's `properties_json` under the key `"fp"` and later decoded using `cbm_minhash_from_hex()`.

The `collect_fp_entries()` function in [`src/pipeline/pass_similarity.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/pipeline/pass_similarity.c) scans the graph buffer for nodes labeled **Function** or **Method**, extracts these hex fingerprints, and builds an array of `fp_entry_t` structures containing the node ID, decoded fingerprint, file path, extension, and qualified name. The array is sorted by qualified name to ensure deterministic pair ownership across parallel runs.

```c
/* Collecting fingerprints from the graph buffer */
fp_entry_t *entries = collect_fp_entries(gbuf, &count);
/* Sorted by qualified name for deterministic processing */

```

## Building the LSH Index for Scalable Lookup

To avoid the O(n²) cost of comparing every function against every other function, the system constructs an LSH index using **32 bands** and **2 rows** per band (`CBM_LSH_BANDS` × `CBM_LSH_ROWS`). The `cbm_lsh_new()` function initializes the index, while `cbm_lsh_insert()` populates it with fingerprint entries.

For each band, the `band_hash()` helper combines two consecutive MinHash values, hashes them with xxHash, and uses the high-order 16 bits (`LSH_BUCKET_MASK = 0xFFFF`) to select a bucket. Any two functions sharing at least one bucket are considered candidates for similarity, reducing the search space from quadratic to linear.

```c
/* Building the LSH index */
cbm_lsh_index_t *idx = cbm_lsh_new();
for (int i = 0; i < entry_count; i++) {
    cbm_lsh_insert(idx, &entries[i]);
}

```

## Querying Candidates and Emitting SIMILAR_TO Edges

Parallel workers execute the similarity search. For each source entry, `cbm_lsh_query_into()` retrieves candidate entries that collide in at least one LSH bucket. A per-run seen-set eliminates duplicate candidates before exact comparison.

The `sim_query_worker()` function in [`pass_similarity.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/pass_similarity.c) computes precise Jaccard similarity using `cbm_minhash_jaccard()`, which counts matching positions in the two 64-element signatures. A `SIMILAR_TO` edge is emitted only when three conditions are met:

- **Jaccard similarity ≥ 0.95** (`CBM_MINHASH_JACCARD_THRESHOLD`)
- **Matching file extensions** ensuring language-specific comparisons
- **Below the edge cap** of 10 edges per node (`CBM_MINHASH_MAX_EDGES_PER_NODE`)

```c
/* Inside sim_query_worker() in src/pipeline/pass_similarity.c */
double j = cbm_minhash_jaccard(&fp, candidate->fingerprint);
if (j >= CBM_MINHASH_JACCARD_THRESHOLD && 
    strcmp(entry->file_ext, candidate->file_ext) == 0) {
    /* Emit the SIMILAR_TO edge */
    cbm_gbuf_insert_edge(gbuf, entry->node_id, candidate->node_id, 
                        "SIMILAR_TO", similarity_props);
}

```

## Merging and Persisting Results

After all workers complete, the `merge_sim_edges()` function sequentially merges buffered edges back into the graph buffer via `cbm_gbuf_insert_edge()`. This produces the final graph containing `SIMILAR_TO` edges that connect near-duplicate functions across the entire codebase, enabling downstream analysis of code duplication patterns.

## Key Parameters and Thresholds

The implementation uses carefully tuned constants to balance recall and precision:

- **`CBM_MINHASH_K` (64)**: Number of hash permutations in the MinHash signature
- **`CBM_LSH_BANDS` (32)**: Number of bands for LSH bucketing
- **`CBM_LSH_ROWS` (2)**: Rows per band (theoretical LSH threshold ≈ 0.177)
- **`CBM_MINHASH_JACCARD_THRESHOLD` (0.95)**: Strict filter for edge emission
- **`CBM_MINHASH_MAX_EDGES_PER_NODE` (10)**: Prevents edge explosion in utility-heavy files

The coarse LSH threshold of approximately 0.177 ensures high recall by generating candidates, while the 0.95 Jaccard requirement guarantees precision by filtering out false positives from hash collisions.

## Summary

- **MinHash fingerprints** are generated from normalized AST trigrams using 64 xxHash permutations in `cbm_minhash_compute()` within [`src/simhash/minhash.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/simhash/minhash.c).
- **LSH indexing** uses 32 bands with 2 rows each to reduce the search space from O(n²) to O(n) candidate generation via `cbm_lsh_insert()` and `cbm_lsh_query_into()`.
- **Strict filtering** requires Jaccard similarity ≥ 0.95 and matching file extensions before creating `SIMILAR_TO` edges in `sim_query_worker()`.
- **Parallel processing** with deterministic sorting and per-node edge caps ensures reproducible, scalable near-clone detection across the codebase.

## Frequently Asked Questions

### What is the SIMILAR_TO edge in codebase-memory-mcp?

The `SIMILAR_TO` edge represents a near-duplicate relationship between two functions or methods in the codebase graph. It indicates that the connected nodes share structural similarity with Jaccard similarity ≥ 0.95, as detected by the MinHash LSH pipeline stage.

### How does the LSH index avoid comparing every function to every other function?

The LSH index partitions each 64-element MinHash signature into 32 bands of 2 rows each. Functions are hashed into buckets based on band combinations, and only functions sharing at least one bucket are compared. This reduces the complexity from quadratic to linear while maintaining high recall for similar pairs.

### Why is the Jaccard threshold set to 0.95 instead of the theoretical LSH threshold?

The theoretical LSH threshold of approximately 0.177 (calculated as (1/32)^(1/2)) is intentionally coarse to ensure high recall and candidate generation. The 0.95 threshold acts as a precision filter, eliminating false positives from hash collisions and ensuring only true near-clones receive `SIMILAR_TO` edges.

### Where are the fingerprinting and similarity functions implemented?

The core MinHash logic resides in [`src/simhash/minhash.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/simhash/minhash.c) (functions like `cbm_minhash_compute()`, `cbm_minhash_jaccard()`, and the LSH index management), while the pipeline orchestration and edge creation happen in [`src/pipeline/pass_similarity.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/pipeline/pass_similarity.c) (functions like `collect_fp_entries()` and `sim_query_worker()`).