SimHash Near-Clone Detection for SIMILAR_TO Edges in Codebase Memory

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, 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 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 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 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 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:

/* 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, 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:

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

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