Scalable Entity Deduplication with Fuzzy Matching in Semantica

Semantica provides a high-performance, configurable duplicate detection engine that uses vector-based similarity and Union-Find grouping to identify fuzzy-matching entities in knowledge graphs at scale.

This article explores the architecture and implementation of scalable entity deduplication in the semantica-agi/semantica repository, focusing on the fuzzy matching algorithms, confidence scoring mechanisms, and incremental processing capabilities that enable efficient duplicate detection across large knowledge graphs.

Core Architecture and Components

The deduplication subsystem centers on three primary abstractions defined in semantica/deduplication/duplicate_detector.py: the orchestration engine, candidate pairs, and transitive groups.

DuplicateDetector Orchestration Engine

The DuplicateDetector class serves as the central orchestrator, managing similarity calculation, candidate filtering, and group formation. Initialized through DuplicateDetector.__init__ (lines 75-94), the detector configures a SimilarityCalculator instance, validates threshold parameters, and initializes a ProgressTracker for long-running operations.

The detector supports both batch processing for static datasets and incremental detection for streaming pipelines, maintaining consistent memory profiles through configurable blocking strategies and result limits.

DuplicateCandidate and DuplicateGroup Data Models

The system uses two primary data structures to represent detection results. The DuplicateCandidate class (lines 52-61) encapsulates pairs of potentially duplicate entities alongside confidence scores and descriptive reasoning (e.g., ['exact_name_match', 'same_type']). Created via _create_duplicate_candidate, these objects receive additional confidence boosts for exact property matches and type alignment.

The DuplicateGroup class (lines 64-71) represents transitive closures of duplicate entities—clusters where member A matches member B, and B matches C, implying A matches C. These groups aggregate pairwise confidences and elect a representative entity based on data completeness.

Similarity Calculation and Candidate Generation

The detection pipeline decouples similarity computation from candidate ranking, enabling flexible scaling strategies.

Batch Pairwise Similarity with Blocking

Similarity calculations delegate to SimilarityCalculator in semantica/deduplication/similarity_calculator.py. The batch_calculate_similarity method computes pairwise similarities across entity sets, implementing optional blocking to reduce the computational complexity from O(N²) to manageable subsets based on shared attributes like entity type or name prefixes.

For relationship deduplication, the calculator applies weighted string similarity (60% predicate match, 40% object match) to handle semantic variations in relationship expressions.

Confidence Thresholding and Result Limits

The detect_duplicates method iterates over similarity pairs to construct DuplicateCandidate objects, immediately filtering candidates that fall below the configured confidence_threshold or exhibit type mismatches. Result cardinality is controlled centrally in _apply_result_limits (lines 76-88), which:

1. Filters candidates by min_similarity
2. Sorts results by the configured sort_by field (defaulting to confidence)
3. Applies global max_results caps and per-entity top_k_per_entity limits

This layered filtering ensures that only high-quality candidates proceed to the computationally expensive group formation stage.

Transitive Group Formation with Union-Find

After candidate generation, the system resolves transitive duplication relationships using Union-Find (disjoint-set) algorithms.

Building Duplicate Groups

The _build_duplicate_groups method (lines 84-90) maps each entity ID to a group index, merging groups when a candidate links two previously separate clusters. This approach efficiently handles the transitive property of duplication: if entity A is a duplicate of B, and B is a duplicate of C, all three belong to the same equivalence class regardless of whether A and C were directly compared.

Representative Selection and Confidence Aggregation

Once groups are formed, _calculate_group_confidence computes a weighted average of pairwise similarity scores within each group, applying boosts for larger clusters to reflect increased certainty. The _select_representative method identifies the most "complete" entity—the one with the highest sum of properties and relationships—to serve as the canonical representation for the duplicate group.

Relationship Deduplication Strategies

Entity deduplication represents only one facet of the system. The detect_relationship_duplicates method (lines 56-70) handles relationship-level deduplication through two distinct modes:

• Legacy exact-match mode: Requires strict equality on subject, predicate, and object
• Semantic mode (semantic_v2): Applies predicate synonym mapping and literal normalization (e.g., "Steve Jobs" vs "Steve J.") to identify semantically equivalent relationships despite surface-level differences

In semantic mode, the detector calculates weighted similarity scores and applies configurable thresholds to determine duplication status.

Incremental Detection for Streaming Pipelines

For production environments processing continuous data streams, the incremental_detect method (lines 49-58) enables efficient duplicate detection without recomputing the full pairwise matrix. This method accepts a batch of new entities and compares them against an existing corpus, reusing the same similarity and confidence logic while preserving the scalability characteristics of the batch processor.

This incremental approach is essential for long-running ETL jobs where reprocessing historical data would be prohibitively expensive.

Configuration and Observability

The deduplication engine exposes extensive configuration options through constructor arguments and the CLI interface in semantica/cli/deduplicate.py:

• similarity_threshold / confidence_threshold: Control detection sensitivity
• use_clustering: Toggle transitive group formation
• max_results, top_k_per_entity, min_similarity, sort_by: Manage output volume and ordering

All public methods emit progress events via ProgressTracker and structured logging through the centralized logger, making the deduplication process observable in both interactive notebooks and production batch jobs.

Practical Implementation Examples

Basic Entity Deduplication

from semantica.deduplication import DuplicateDetector

entities = [
    {"id": "1", "name": "Apple Inc.", "type": "Company"},
    {"id": "2", "name": "Apple",      "type": "Company"},
    {"id": "3", "name": "Microsoft",  "type": "Company"},
]

detector = DuplicateDetector(similarity_threshold=0.8, confidence_threshold=0.7)
candidates = detector.detect_duplicates(entities)

for cand in candidates:
    print(f"{cand.entity1['name']} ↔ {cand.entity2['name']} "
          f"(conf={cand.confidence:.2f}, reasons={cand.reasons})")

# → Apple Inc. ↔ Apple (conf=0.80, reasons=['exact_name_match', 'same_type'])

Transitive Group Formation

groups = detector.detect_duplicate_groups(entities)

for g in groups:
    rep = g.representative or {}
    print(f"Group of {len(g.entities)} entities, confidence={g.confidence:.2f}, "
          f"representative={rep.get('name')}")

# → Group of 2 entities, confidence=0.80, representative=Apple Inc.

Incremental Stream Processing

new_entities = [{"id": "4", "name": "Apple Corp.", "type": "Company"}]
existing = entities   # previously processed set

inc_cands = detector.incremental_detect(new_entities, existing)
print(inc_cands)   # contains a candidate linking "Apple Corp." with "Apple Inc."

Semantic Relationship Deduplication

relationships = [
    {"subject": "Apple", "predicate": "founded_by", "object": "Steve Jobs"},
    {"subject": "Apple", "predicate": "founded_by", "object": "Steve J."},
]

dup_rel = detector.detect_relationship_duplicates(
    relationships,
    mode="semantic_v2",
    predicate_synonym_map={"founded_by": "founded_by"},
    literal_normalization_enabled=True,
    threshold=0.6,
)

print(dup_rel)   # -> [(rel1, rel2)] because predicates match and objects normalize similarly

Summary

• Modular Architecture: The system separates similarity calculation (SimilarityCalculator), candidate ranking (DuplicateCandidate), and group aggregation (DuplicateGroup) to enable both batch and incremental workflows.

• Union-Find Grouping: Transitive duplicate relationships are resolved using efficient Union-Find algorithms in _build_duplicate_groups, ensuring that indirect duplication chains are correctly identified.

• Configurable Matching: Both entity and relationship deduplication support multiple modes, from exact matching to semantic normalization with synonym handling.

• Scalable Processing: Optional blocking strategies and incremental detection methods (incremental_detect) keep memory and CPU usage tractable for large knowledge graphs.

• Production Observability: Integrated progress tracking and structured logging via ProgressTracker provide visibility into long-running deduplication tasks.

Frequently Asked Questions

How does Semantica handle transitive duplicate relationships?

Semantica uses a Union-Find (disjoint-set) data structure in the _build_duplicate_groups method to resolve transitive relationships. If entity A matches B, and B matches C, the algorithm merges all three into a single DuplicateGroup even if A and C were never directly compared. This ensures complete deduplication clusters without requiring O(N²) comparisons across the entire dataset.

What is the difference between similarity_threshold and confidence_threshold?

The similarity_threshold parameter controls the raw vector or string similarity scores calculated by SimilarityCalculator, while confidence_threshold applies to the final DuplicateCandidate objects after additional boosts (exact name matches, property alignment) and penalties are applied. The confidence score represents the system's final certainty that two entities are duplicates, whereas similarity reflects only the initial vector distance.

Can the system detect duplicates in streaming data without reprocessing historical entities?

Yes. The incremental_detect method in duplicate_detector.py (lines 49-58) compares new entities against an existing corpus without recomputing similarities among historical data. This preserves the scalability characteristics of the batch processor while supporting real-time or near-real-time deduplication pipelines.

How does relationship deduplication differ from entity deduplication?

While entity deduplication focuses on fuzzy matching of node properties (names, attributes, types), relationship deduplication in detect_relationship_duplicates evaluates the semantic equivalence of edges. In semantic_v2 mode, the system applies predicate synonym mapping and literal normalization (e.g., handling abbreviations or alternate spellings) with a weighted scoring system (60% predicate similarity, 40% object similarity) rather than requiring exact string matches on subject-predicate-object triples.

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