Wikilink Graph Indexing: Graph Algorithms

Introduction: The Scale of Personal Knowledge Graphs

The fundamental innovation of modern personal knowledge management (PKM) software—pioneered by Roam Research and perfected by Obsidian—is the bidirectional wikilink ([[Target]]). By breaking away from rigid hierarchical folder trees and enabling relational links between arbitrary thoughts, wikilinks transform flat documents into an associative, interconnected knowledge graph.

In a modest vault of 500 notes, querying backlinks or rendering a local graph view is trivial. However, for power users who accumulate 20,000, 50,000, or 100,000 notes over a career, graph maintenance becomes computationally demanding.

Knowledge Graph Topography (Nodes & Bidirectional Edges):
┌─────────────────────────┐               ┌─────────────────────────┐
│ [[2026-10-10 Meeting]]  │──────────────►│ [[ADR-042 Search Engine]]│
│ Outbound Link           │               │ Inbound Backlink        │
└────────────┬────────────┘               └────────────┬────────────┘
             │                                         │
             ▼                                         ▼
┌─────────────────────────┐               ┌─────────────────────────┐
│ [[Julian Thorne]]       │◄──────────────│ [[SQLite FTS5]]         │
│ Attendee Node           │               │ Concept Node            │
└─────────────────────────┘               └─────────────────────────┘

When a user opens a note, renames a file, or opens their graph view, the desktop application must resolve:

1. Forward Links: What other files does this document reference?
2. Backlinks: What external documents point to this file?
3. Unlinked Mentions: Where does this note’s title appear as plain text across the entire vault without brackets?
4. Graph Layout Physics: How do thousands of interconnected nodes arrange themselves in 2D space at 60 frames per second?

In this deep architectural teardown, we explore the data structures, regex tokenizers, and graph traversal algorithms required to index and query 50,000-note wikilink graphs with sub-millisecond latency.

---

1. Data Structures for In-Memory Graph Representation

In graph theory, a directed graph $G = (V, E)$ consists of vertices $V$ (notes) and directed edges $E$ (wikilinks).

1.1 Why Adjacency Matrices Fail at Scale

In an adjacency matrix, a graph with $N = 50,000$ notes requires a matrix of size $50,000 \times 50,000 = 2.5 \times 10^9$ entries. Even using single-bit boolean flags, this consumes 312 megabytes of RAM just to represent edge existence. Furthermore, querying backlinks for a single note requires scanning an entire 50,000-element column ($O(N)$ complexity).

1.2 The Dual-Map Adjacency Architecture

Because knowledge graphs are extremely sparse (average node degree $d \approx 4$ to $12$ links), Oyma utilizes a dual-map adjacency structure:

// Core Knowledge Graph Data Structures
export interface GraphNode {
  id: string;             // Vault-relative path: "40-Meetings/2026-10-10.md"
  title: string;          // Human-readable title
  aliases: string[];      // YAML frontmatter aliases
  headings: Set<string>;  // Normalized heading anchors
  mtime: number;          // File modification timestamp
}

export class KnowledgeGraphIndex {
  // Primary node dictionary: ID -> Node
  private nodes: Map<string, GraphNode> = new Map();

  // Forward edges: Source ID -> Set of Target IDs
  private forwardLinks: Map<string, Set<string>> = new Map();

  // Inverted backlinks: Target ID -> Set of Source IDs
  private backlinks: Map<string, Set<string>> = new Map();

  // Alias lookup index: Alias (lowercase) -> Target ID
  private aliasIndex: Map<string, string> = new Map();
}

With this dual-map design:

• Querying outbound links (forwardLinks.get(noteId)) is $O(1)$.
• Querying inbound backlinks (backlinks.get(noteId)) is $O(1)$.
• Total memory consumption for 50,000 notes and 250,000 edges is less than 18 megabytes of RAM.

---

2. Tokenizing Wikilinks with Sub-Microsecond Precision

Extracting wikilinks from a Markdown file can be performed via full AST parsing or optimized regular expression scanning.

While AST parsing is required for rich live-preview rendering, scanning files during background indexing must be as fast as possible.

// High-performance regex tokenization for wikilink extraction
// Matches: [[Target]], [[Target|Alias]], [[Target#Heading]], [[Target#Heading|Alias]]
const WIKILINK_SCANNER = /\[\[([^\]\|\n#]+)(?:#([^\]\|\n]+))?(?:\|([^\]\n]+))?\]\]/g;

export function extractLinksFromMarkdown(content: string): ExtractedLink[] {
  const links: ExtractedLink[] = [];
  let match: RegExpExecArray | null;

  while ((match = WIKILINK_SCANNER.exec(content)) !== null) {
    links.push({
      raw: match[0],
      targetName: match[1].trim(),
      headingAnchor: match[2] ? match[2].trim() : undefined,
      alias: match[3] ? match[3].trim() : undefined,
      offset: match.index,
    });
  }

  return links;
}

2.1 Code Block Immunity

A common bug in naive wikilink parsers is extracting links that appear inside fenced code blocks or inline backticks:

Here is an example in documentation:
```markdown
Do not link this [[Internal Note]] inside code!
```

To prevent phantom graph edges, our scanner skips code fences by maintaining a lightweight block-state machine during linear scanning, ignoring any tokens between matching triple-backtick markers.

---

3. Real-Time Link Renaming and Graph Refactoring

One of the most valuable features in modern knowledge tools is automatic link refactoring. When a user renames Project Apollo.md to Project Artemis.md, every wikilink across all 50,000 notes that pointed to Apollo must be updated atomically.

Automatic Rename Refactoring Flow:
[User Renames: "Project Apollo" ──► "Project Artemis"]
                          │
                          ▼
[Query backlinks.get("Project Apollo")] ──► O(1) Lookup: 42 Referencing Notes
                          │
                          ▼
[For Each Referencing Note: Batch Atomic Update]
  ├── Replace [[Project Apollo]] with [[Project Artemis]]
  ├── Preserve Custom Aliases: [[Project Apollo|Old Project]] ──► [[Project Artemis|Old Project]]
  └── Write Atomically via APFS RENAME_SWAP Primitive
                          │
                          ▼
[Update In-Memory Index (1.4ms Total Time)]

Because our inverted backlink map provides instantaneous $O(1)$ identification of referencing documents, Oyma does not scan the entire vault. If 42 notes link to Apollo, only those 42 files are read, rewritten, and saved, completing the global refactor in under 30 milliseconds.

---

4. Graph View Physics: Barnes-Hut Quadtree Acceleration

The visual interactive network graph is a signature feature of personal knowledge tools. Nodes represent notes, and edges represent links. The layout is calculated using force-directed physics:

• Repulsion: All nodes repel each other (Coulomb’s Law: $F \propto 1/r^2$).
• Attraction: Linked nodes attract each other like springs (Hooke’s Law: $F \propto r$).

4.1 The $O(N^2)$ N-Body Problem

Computing pairwise repulsion across $N = 10,000$ nodes requires evaluating $10,000 \times 10,000 = 100,000,000$ force calculations per animation frame. At 60 FPS, this exceeds the compute budget of even high-end CPUs.

4.2 The Barnes-Hut $O(N \log N)$ Optimization

To achieve 60 FPS, Oyma utilizes the Barnes-Hut algorithm:

1. Recursively partition 2D space into a quadtree.
2. For distant clusters of nodes, treat the entire cluster as a single center of mass.
3. If the ratio of cell size $s$ to distance $d$ satisfies $s/d < \theta$ (where $\theta \approx 0.8$), calculate repulsion against the cluster center rather than individual nodes.

This drops computational complexity from $O(N^2)$ to $O(N \log N)$, enabling buttery-smooth 60 FPS physics across vaults containing tens of thousands of interconnected notes.

---

5. Summary: High-Throughput Relational Knowledge

A personal knowledge base is only as powerful as the connections it illuminates. By employing dual-map adjacency structures, code-block-immune tokenizers, instant backlink lookups, and Barnes-Hut quadtree physics, desktop applications can deliver frictionless graph navigation across decades of accumulated intellectual assets.

In Oyma, these graph indexing engines work silently in the background, ensuring that your meeting notes and Obsidian-compatible files remain instantly navigable and permanently interconnected.

---

6. Incremental Index Updates via Difference Graph Traversals

When a user modifies a note in a 50,000-file vault, re-parsing the entire knowledge graph is completely unacceptable.

Oyma implements an Incremental Difference Graph Traversal:

1. When FSEvents reports a file modification on NoteA.md:
2. The index retrieves the previously cached outbound links: oldLinks = forwardLinks.get("NoteA").
3. The tokenizer extracts the newly written links: newLinks = extractLinks(newContent).
4. The engine computes the symmetric difference:
   • Removed Links: removed = oldLinks - newLinks. For each removed target, delete NoteA from backlinks.get(target).
   • Added Links: added = newLinks - oldLinks. For each added target, insert NoteA into backlinks.get(target).
5. Update forwardLinks.set("NoteA", newLinks).

This incremental update touches only the specific nodes affected by the edit, updating the in-memory graph in less than 1.2 milliseconds.

---

7. Fast Case-Insensitive Fuzzy Heading Anchor Resolution

In Markdown vaults, wikilinks frequently reference specific section headings: [[2026-10-10 Architecture Sync#FTS5 Memory Budget]].

Resolving heading anchors introduces two challenges:

• Heading Normalization: In source Markdown, headings contain formatting, wikilinks, and special punctuation (## 3. FTS5 Memory Budget (16 MB)).
• Case Sensitivity: Users frequently type anchors with varying case: #fts5-memory-budget or #FTS5 Memory Budget.

To achieve instantaneous heading resolution:

• Each node stores a pre-computed hash set of normalized slugified headings alongside raw heading texts.
• Anchor lookups normalize both the query anchor and document headings using GitHub’s slugification algorithm, resolving targets in $O(1)$ time without linear document scanning.

---

8. WebGL Instanced Geometry Optimization for 100,000 Node Graphs

When visualizing massive vaults in the interactive Graph View, rendering 50,000 nodes and 200,000 link lines using standard 2D canvas APIs (CanvasRenderingContext2D) causes severe frame rate drops (less than 12 FPS).

Oyma utilizes a custom WebGL Instanced Renderer:

• Instanced Circle Meshes: All 50,000 node circles are drawn in a single WebGL draw call (gl.drawArraysInstanced()) using GPU vertex buffers containing node positions, radii, and color tints.
• Batched Line Buffers: Edges are packed into a contiguous Float32Array line buffer and rendered in a single draw pass.
• Hardware Acceleration: Force-directed layout physics updates are uploaded directly to GPU uniform buffers, achieving fluid 60 FPS pan and zoom even across gargantuan enterprise knowledge graphs.