brain of mat kelcey

e10.2 tgraph crawl order example

September 21, 2009

let's consider an example of the crawl order for tgraph...

we seed our frontier with 'a' and bootstrap cost of 0.

fetching the info for 'a' shows 2 outedges to 'b' and 'c', from our cost formula these all have cost 0 + 1 + Log10(2+1) = 1.6

our frontier becomes [ {b,1.6}, {c,1.6} ]

next is 'b' and see it has an outdegree of 3, these nodes, b1 -> b3, all have a cost of 1.6 + 1 + Log10(3+1) = 3.2

our frontier becomes [ {c,1.6}, {b1,3.2}, {b2,3.2}, {b3,3.2} ]

next is 'c' with an outdegree of 15. these 15 nodes, c1 -> c15, have cost 1.6 + 1 + Log10(16) = 3.8

our frontier is now [ {b1,3.2}, {b2,3.2}, {b3,3.2}, {c1,3.8} ... {c15,3.8} ]

we would then continue with the 'b' nodes before the 'c' ones

note that this cost system is more than just an ordering, it allows an element at depth n+1 to be checked an element at depth n, if the cost of the latter is high enough.