BSN-1003 - Building the Bidirectional Graph

Living Document Notice
Published 2026-09-12. The evolving architecture, revisions, and connected notes for this dispatch live in the Stax Digital Garden.

Building the Bidirectional Graph

Summary

Personal knowledge graphs require instantaneous traversal across forward links and backward references. Hash-map adjacency tables introduce pointer fragmentation and cache misses when tracking hundreds of thousands of cross-document edges across 50,000 notes.

Bosun structures bidirectional note references using twin Compressed Sparse Row (CSR) index structures. Representing source nodes, target nodes, and edge weights as contiguous 32-bit integer slices allows graph traversals to leverage CPU cache locality and hardware prefetching.

Compressed Sparse Row Memory Layout

A standard adjacency list stores an array of heap-allocated vectors, requiring one heap allocation per node. In contrast, a CSR graph flattens all edges into two contiguous memory arrays: row_offsets and column_indices.

pub struct CsrGraph {
    /// Offsets into column_indices for each node ID
    pub row_offsets: Vec<u32>,
    /// Contiguous target node IDs
    pub column_indices: Vec<u32>,
    /// Edge line numbers for source linking
    pub edge_lines: Vec<u32>,
}

To retrieve outgoing links for NodeId(k), the graph engine reads index bounds from row_offsets[k] to row_offsets[k + 1]. The target node identifiers reside in column_indices within that exact slice, enabling sequential memory access during graph traversals.

An inverse CSR structure maintains the reverse graph mapping target nodes back to origin documents. Both forward and reverse indices share identical node identifier keys, eliminating translation overhead during bidirectional queries.

Incremental Mutation without Global Re-indexing

Rebuilding full CSR arrays on every keystroke incurs unnecessary copying overhead. Bosun pairs the static CSR base with an in-memory mutable delta buffer.

pub struct IncrementalGraph {
    base_forward: CsrGraph,
    base_backward: CsrGraph,
    forward_deltas: HashMap<u32, SmallVec<[u32; 8]>>,
    backward_deltas: HashMap<u32, SmallVec<[u32; 8]>>,
    deleted_edges: HashSet<(u32, u32)>,
}

When a document’s outgoing links change, only its entry in forward_deltas is updated. Query operations evaluate the base CSR slice merged with the small delta array. A background thread periodically merges delta buffers into a new immutable CSR snapshot when accumulated mutations exceed 10,000 operations.

This hybrid indexing strategy guarantees lock-free reads for UI rendering threads while background worker threads handle compaction.

Cache Locality and Vectorized Traversal

Because column_indices stores contiguous 32-bit integers, search operations within an edge list utilize SIMD vector instructions. When checking whether document A links to document B, the engine loads eight 32-bit integers at once into an AVX2 register.

This vector comparison runs in parallel across lane registers, replacing sequential branching loops. Transitive queries, such as 2-hop neighborhood discovery, traverse these contiguous arrays without dereferencing scattered heap pointers.

Hardware prefetchers detect linear memory access patterns across CSR index buffers, preloading downstream edge arrays into L1 and L2 caches ahead of execution cycles.

Graph Query Latencies and Memory Ceilings

The table below shows performance measurements for graph construction and query execution across increasing vault sizes.

Vault Notes	Total Edges	1-Hop Lookup Latency	2-Hop Path Latency	CSR Memory Footprint
5,000	28,400	18 ns	340 ns	248 KB
15,000	92,100	22 ns	410 ns	780 KB
30,000	194,500	25 ns	490 ns	1.62 MB
50,000	342,000	28 ns	580 ns	2.85 MB
100,000	710,000	32 ns	720 ns	5.92 MB

---

• Directus Target: bosunpkm-blog
• Garden Source Reference: MOC - Bosun PKM Engine, MOC - Bosun PKM Tools, MOC - The Plain-Text Longevity Standard