Graph traversal is exponential in depth

How it behaves

One input on the horizontal axis, the others held fixed.

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

• d = 100, 3 hops → 1,000,000
• 4 hops bidirectionally → 20,000 instead of 100,000,000
• GraphQL: 100 × 100 × 100 objects for one call at depth 3

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

• Specialized Processing Models

  What do you build when a query predicate cannot be reduced to a range over an ordered key?

  $$d^k;2\cdot d^{k/2}$$

  Read it in place →

• Interfaces & Formats

  What can two parties agree on when they cannot talk to each other?

  $$100\times 100\times 100=1,000,000\text{objects at depth 3}$$

  100 children per level = $d$ · depth = $k$

  Read it in place →