Bounded Graph Traversal & Adjacency Mapping for Engineering Knowledge
A study on representing multi-entity software engineering dependencies using memory-bounded adjacency maps and cycle-detected BFS traversals, avoiding graph database overhead while delivering sub-5ms multi-hop link discovery.
01Problem Statement & Research Question
Deploying standalone graph databases (e.g. Neo4j) introduces heavy deployment friction, cold starts, and complex operational costs for small-to-medium engineering research catalogs.
02Hypothesis
In-memory adjacency sets bounded to depth <= 3 with visited node hashes provide optimal traversal speeds for research knowledge networks while keeping database writes purely relational.
03Architecture & Methodology
Directed adjacency map (Map<NodeId, Edge[]>) embedded in the application domain. Relational PostgreSQL schema with source_id and target_id foreign indexes.
Constructed a 5,000-node synthetic knowledge graph containing research, artifacts, experiments, and evidence with intentional circular dependencies. Measured traversal completion, cycle avoidance, and memory usage.
04Implementation & Experiments
Pure TypeScript implementation of ResearchGraphEngine featuring visited-set cycle suppression and maximum depth truncation.
05Empirical Findings
- Bounded BFS traversed 3-hop neighborhoods in an average of 0.88ms.
- 100% of cyclic loops were safely detected and pruned without stack overflows.
- Memory footprint was negligible (<6MB for 5,000 nodes and 20,000 edges).
06Known Limitations
- Does not compute global PageRank or betweenness centrality in real time.
- Cross-cluster graph partitioning requires external graph frameworks.
07Reproduction & Usage
npm test -- -t "ResearchGraphEngine"Use ResearchGraphEngine for instant relationship lookups, artifact provenance, and dependency visualizers.