holographic_memory/core/cognition/
gaps.rs

1// Copyright 2024-2026 WritersLogic Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! Epistemic gap detection.
5//!
6//! Compares an entity's relation profile against its peers to find
7//! missing relations. For example, if most cities have a `country` relation
8//! but city X does not, that is a gap.
9
10use fxhash::{FxHashMap, FxHashSet};
11
12use crate::core::triple_store::TripleStore;
13
14/// A detected knowledge gap: an entity is missing a relation that its peers have.
15#[derive(Clone, Debug)]
16pub struct KnowledgeGap {
17    /// The entity missing the relation.
18    pub entity: String,
19    /// The relation that is missing.
20    pub missing_relation: String,
21    /// Peer entities that do have this relation (evidence).
22    pub peers_with_relation: Vec<String>,
23    /// Fraction of peers that have this relation (0.0 - 1.0).
24    pub peer_coverage: f64,
25}
26
27/// Detects knowledge gaps by comparing entity profiles to peer profiles.
28pub struct GapDetector;
29
30impl GapDetector {
31    /// Find entities that are missing relations their peers have.
32    ///
33    /// Two entities are peers if they share at least `min_shared_relations` relations.
34    /// A gap is reported when `>= min_peer_coverage` fraction of peers have a relation
35    /// that the entity lacks.
36    pub fn detect(
37        triple_store: &TripleStore,
38        min_shared_relations: usize,
39        min_peer_coverage: f64,
40    ) -> Vec<KnowledgeGap> {
41        let snapshot = triple_store.snapshot();
42
43        // Build entity -> set of relations (as subject)
44        let mut entity_rels: FxHashMap<String, FxHashSet<String>> = FxHashMap::default();
45        for t in &snapshot {
46            entity_rels
47                .entry(t.subject_id.clone())
48                .or_default()
49                .insert(t.relation_id.clone());
50        }
51
52        // Build relation -> set of subjects (for peer lookup)
53        let mut rel_subjects: FxHashMap<String, FxHashSet<String>> = FxHashMap::default();
54        for t in &snapshot {
55            rel_subjects
56                .entry(t.relation_id.clone())
57                .or_default()
58                .insert(t.subject_id.clone());
59        }
60
61        let mut gaps = Vec::new();
62
63        for (entity, rels) in &entity_rels {
64            // Find peers: other entities sharing >= min_shared_relations
65            let mut peer_candidates: FxHashMap<String, usize> = FxHashMap::default();
66            for rel in rels {
67                if let Some(subjects) = rel_subjects.get(rel) {
68                    for peer in subjects {
69                        if peer != entity {
70                            *peer_candidates.entry(peer.clone()).or_insert(0) += 1;
71                        }
72                    }
73                }
74            }
75
76            let peers: Vec<String> = peer_candidates
77                .into_iter()
78                .filter(|&(_, count)| count >= min_shared_relations)
79                .map(|(id, _)| id)
80                .collect();
81
82            if peers.is_empty() {
83                continue;
84            }
85
86            // Collect all relations that peers have (O(1) lookup via entity_rels)
87            let mut peer_rel_counts: FxHashMap<String, usize> = FxHashMap::default();
88            for peer in &peers {
89                if let Some(peer_rels) = entity_rels.get(peer) {
90                    for rel in peer_rels {
91                        *peer_rel_counts.entry(rel.clone()).or_insert(0) += 1;
92                    }
93                }
94            }
95
96            // Check for gaps: relations the entity doesn't have but peers do
97            let peer_count = peers.len();
98            for (rel, count) in &peer_rel_counts {
99                if rels.contains(rel) {
100                    continue;
101                }
102                let coverage = *count as f64 / peer_count as f64;
103                if coverage >= min_peer_coverage {
104                    let peers_with: Vec<String> = peers
105                        .iter()
106                        .filter(|p| entity_rels.get(*p).is_some_and(|pr| pr.contains(rel)))
107                        .cloned()
108                        .collect();
109
110                    gaps.push(KnowledgeGap {
111                        entity: entity.clone(),
112                        missing_relation: rel.clone(),
113                        peers_with_relation: peers_with,
114                        peer_coverage: coverage,
115                    });
116                }
117            }
118        }
119
120        gaps.sort_by(|a, b| {
121            b.peer_coverage
122                .partial_cmp(&a.peer_coverage)
123                .unwrap_or(std::cmp::Ordering::Equal)
124        });
125        gaps
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use super::*;
132
133    #[test]
134    fn test_detect_gaps() {
135        let store = TripleStore::new();
136        // Paris and Berlin are in Europe and are capitals
137        store.add("paris", "capital_of", "france", "c1");
138        store.add("paris", "located_in", "europe", "c2");
139        store.add("berlin", "capital_of", "germany", "c3");
140        store.add("berlin", "located_in", "europe", "c4");
141        // Tokyo is a capital but missing located_in
142        store.add("tokyo", "capital_of", "japan", "c5");
143
144        let gaps = GapDetector::detect(&store, 1, 0.5);
145
146        let tokyo_gap = gaps
147            .iter()
148            .find(|g| g.entity == "tokyo" && g.missing_relation == "located_in");
149        assert!(tokyo_gap.is_some(), "Tokyo should be missing located_in");
150        let gap = tokyo_gap.unwrap();
151        assert!(gap.peer_coverage >= 0.5);
152        assert!(!gap.peers_with_relation.is_empty());
153    }
154
155    #[test]
156    fn test_no_gaps_when_complete() {
157        let store = TripleStore::new();
158        store.add("a", "r1", "x", "c1");
159        store.add("b", "r1", "y", "c2");
160        // Both have the same relation, no gaps
161        let gaps = GapDetector::detect(&store, 1, 0.5);
162        assert!(gaps.is_empty());
163    }
164
165    #[test]
166    fn test_no_gaps_empty_store() {
167        let store = TripleStore::new();
168        let gaps = GapDetector::detect(&store, 1, 0.5);
169        assert!(gaps.is_empty());
170    }
171
172    #[test]
173    fn test_high_coverage_threshold() {
174        let store = TripleStore::new();
175        store.add("a", "r1", "x", "c1");
176        store.add("a", "r2", "x", "c2");
177        store.add("b", "r1", "y", "c3");
178        // b is missing r2, but only 1 peer has it (100% of 1 peer)
179        // With min_shared=1, a is a peer of b
180        let gaps = GapDetector::detect(&store, 1, 1.0);
181        let b_gap = gaps
182            .iter()
183            .find(|g| g.entity == "b" && g.missing_relation == "r2");
184        assert!(b_gap.is_some());
185    }
186}
holographic_memory/core/cognition/gaps.rs

holographic_memory/core/cognition/
gaps.rs
