# SimHash Near-Clone Detection for SIMILAR_TO Edges in Codebase Memory

> Discover SimHash near-clone detection in Codebase Memory. Learn how this MinHash algorithm finds near-duplicate functions across codebases using SIMILAR_TO edges with Jaccard similarity.

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

---

**Codebase Memory uses a MinHash-based SimHash algorithm to detect near-duplicate functions across codebases, emitting SIMILAR_TO edges when Jaccard similarity exceeds 0.95.**

The `DeusData/codebase-memory-mcp` repository implements a high-performance near-duplicate detection system that identifies structurally similar functions across large-scale projects. This system generates **SIMILAR_TO** edges in the graph database to link near-clone code, enabling developers to track duplication and code reuse patterns. The implementation combines MinHash fingerprinting with Locality-Sensitive Hashing (LSH) to scale efficiently to millions of functions while maintaining high precision.

## How SimHash Near-Clone Detection Works

The detection pipeline operates in five distinct phases, from AST extraction to edge persistence. Each function body is processed independently to generate a compact fingerprint that captures structural similarity.

### AST Normalization and Fingerprint Generation

During extraction, each function’s AST is normalized to a stream of leaf-only token types. Identifiers become `I`, strings become `S`, numbers become `N`, and type annotations become `T`. The system generates **3-token trigrams** from this normalized stream and hashes each trigram with 64 independent xxHash seeds.

In [`src/simhash/minhash.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/simhash/minhash.c), the `cbm_minhash_compute` function implements this logic. It returns a **64-element MinHash signature** (`cbm_minhash_t`) representing the function’s structural fingerprint. Functions with fewer than 30 leaf tokens (controlled by `CBM_MINHASH_MIN_NODES`) are skipped to avoid noise from trivial code snippets.

The resulting 512-character hex string is stored in the node’s JSON properties under the `"fp"` key, as implemented in [`internal/cbm/extract_defs.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/internal/cbm/extract_defs.c) via the `CBMDefinition.fingerprint` interface.

### LSH Index Construction

To avoid comparing every function against every other function, Codebase Memory builds an LSH (Locality-Sensitive Hashing) index. The `cbm_lsh_new` and `cbm_lsh_insert` functions in [`src/simhash/minhash.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/simhash/minhash.c) organize fingerprints into **32 bands with 2 rows each** (defined by `CBM_LSH_BANDS` and `CBM_LSH_ROWS`).

Each signature is split into 32 bands, and each band is hashed into a bucket. Signatures that share at least one band are considered candidates for similarity comparison. This reduces the search space from O(n²) to O(n) while guaranteeing that similar functions collide in at least one bucket with high probability.

### Similarity Scoring and Edge Emission

The `sim_query_worker` function in [`src/pipeline/pass_similarity.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/pipeline/pass_similarity.c) queries the LSH index using `cbm_lsh_query_into` to retrieve candidate pairs. For each candidate, the system computes exact Jaccard similarity using `cbm_minhash_jaccard`, which calculates the ratio of matching slots to total slots (64).

When the Jaccard similarity is **≥ 0.95** (`CBM_MINHASH_JACCARD_THRESHOLD`), a **SIMILAR_TO** edge is created. The edge includes JSON properties annotating the `jaccard` score and a `same_file` boolean indicating whether the clones reside in the same source file. The system caps edges per source node at 10 (`CBM_MINHASH_MAX_EDGES_PER_NODE`) to prevent dense connectivity in the graph.

## Key Constants and Configuration

The following constants in [`src/simhash/minhash.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/simhash/minhash.h) control the detection behavior:

| Constant | Value | Description |
|----------|-------|-------------|
| `CBM_MINHASH_K` | 64 | Number of hash slots per signature |
| `CBM_MINHASH_MIN_NODES` | 30 | Minimum leaf tokens required for fingerprinting |
| `CBM_MINHASH_JACCARD_THRESHOLD` | 0.95 | Similarity threshold for edge creation |
| `CBM_MINHASH_MAX_EDGES_PER_NODE` | 10 | Maximum SIMILAR_TO edges per source node |
| `CBM_LSH_BANDS` | 32 | Number of LSH index bands |
| `CBM_LSH_ROWS` | 2 | Rows per band in the LSH index |

## Implementation Example

The following C code illustrates the core workflow for generating SIMILAR_TO edges:

```c
/* Collect functions with fingerprints */
fp_entry_t *entries = NULL;
int entry_count = collect_fp_entries(gbuf, &entries);

/* Build LSH index */
cbm_lsh_index_t *lsh = cbm_lsh_new();
for (int i = 0; i < entry_count; ++i) {
    cbm_lsh_entry_t e = {
        .node_id        = entries[i].node_id,
        .fingerprint    = &entries[i].fp,
        .file_path      = entries[i].file_path,
        .file_ext       = entries[i].ext,
        .qualified_name = entries[i].qn,
    };
    cbm_lsh_insert(lsh, &e);
}

/* Query and emit edges */
for (int i = 0; i < entry_count; ++i) {
    const cbm_lsh_entry_t **candidates = NULL;
    int cand_cnt = 0;
    cbm_lsh_query(lsh, &entries[i].fp, &candidates, &cand_cnt);

    for (int c = 0; c < cand_cnt; ++c) {
        const cbm_lsh_entry_t *cand = candidates[c];
        if (cand->node_id == entries[i].node_id) continue;
        if (strcmp(entries[i].ext, cand->file_ext) != 0) continue;
        
        double j = cbm_minhash_jaccard(&entries[i].fp, cand->fingerprint);
        if (j < CBM_MINHASH_JACCARD_THRESHOLD) continue;

        bool same_file = strcmp(entries[i].file_path, cand->file_path) == 0;
        char props[256];
        snprintf(props, sizeof(props),
                 "{\"jaccard\":%.3f,\"same_file\":%s}",
                 j, same_file ? "true" : "false");

        cbm_gbuf_insert_edge(gbuf, entries[i].node_id, cand->node_id, 
                            "SIMILAR_TO", props);
    }
}

```

The production implementation resides in [`src/pipeline/pass_similarity.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/pipeline/pass_similarity.c), specifically within the `sim_query_worker` and `merge_sim_edges` functions.

## Adjusting Detection Sensitivity

You can tune the near-clone detection behavior by modifying constants in [`src/simhash/minhash.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/simhash/minhash.h):

- **Lower similarity threshold**: Change `CBM_MINHASH_JACCARD_THRESHOLD` from 0.95 to 0.90 for more aggressive detection of partial clones.
- **Finer granularity**: Increase `CBM_MINHASH_K` to 128 for more precise similarity estimates (requires updating `CBM_MINHASH_HEX_LEN` accordingly).
- **Reduce noise**: Lower `CBM_MINHASH_MAX_EDGES_PER_NODE` to limit edges from utility functions frequently shared across files.
- **Cross-language detection**: Remove the `strcmp(src->ext, cand->file_ext)` guard in `sim_query_worker` to allow similarity matching across different programming languages.

## Summary

- **MinHash fingerprinting** in [`src/simhash/minhash.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/simhash/minhash.c) generates 64-element signatures from normalized AST trigrams, stored as 512-character hex strings in node properties.
- **LSH indexing** organizes fingerprints into 32 bands to efficiently identify candidate pairs without exhaustive comparison.
- **Exact Jaccard scoring** filters candidates, emitting SIMILAR_TO edges only when similarity reaches 0.95 or higher.
- **Edge properties** include the Jaccard score and `same_file` flag, with a default cap of 10 edges per node to maintain graph sparsity.
- **Configuration** is controlled via constants in [`minhash.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/minhash.h), allowing customization of thresholds, granularity, and noise reduction.

## Frequently Asked Questions

### What is the minimum code size required for SimHash fingerprinting?

Codebase Memory requires at least 30 leaf tokens (`CBM_MINHASH_MIN_NODES`) to generate a fingerprint. Functions smaller than this threshold are skipped during the extraction phase in [`internal/cbm/extract_defs.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/internal/cbm/extract_defs.c) to avoid noise from trivial getter/setter methods or small utility functions.

### How does the LSH index improve performance when detecting near-clones?

The LSH index reduces the complexity from O(n²) pairwise comparisons to O(n) by hashing signatures into 32 bands. Only functions sharing at least one band (bucket collision) are compared using exact Jaccard similarity. This probabilistic approach, implemented in `cbm_lsh_insert` and `cbm_lsh_query`, ensures that truly similar functions are found while filtering out 99% of dissimilar pairs.

### Can SimHash detection work across different programming languages?

By default, the similarity pass in [`src/pipeline/pass_similarity.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/pipeline/pass_similarity.c) filters out cross-language candidates by comparing file extensions (`strcmp(src->ext, cand->file_ext)`). However, you can enable cross-language detection by removing this guard, allowing the structural MinHash comparison to match similar algorithms implemented in different languages.

### How do I adjust the similarity threshold for near-clone detection?

Modify the `CBM_MINHASH_JACCARD_THRESHOLD` constant in [`src/simhash/minhash.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/simhash/minhash.h). The default value of 0.95 ensures high precision for near-identical clones. Lowering this to 0.85 or 0.90 will detect more partial clones and refactored code, though this may increase false positives requiring manual review.