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

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 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.

/* 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 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.

/* 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.

/* 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 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)

/* 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.
• 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 (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 (functions like collect_fp_entries() and sim_query_worker()).

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}