Graph Traversal

From View

Jump to: navigation, search



Graph Traversal applications must traverse a number of objects and examine characteristics of those objects. Applications typically involve indirect lookups and little computation.

Uniprocessor Mapping

An algorithm that requires little processing and sequential access of successive graph nodes may be equivalent to pointer chasing, without much chance for more efficient processing. Often, though, the reality is better: there may be locality in accesses to the graph, or there might be some processing per node that can reduce the effective cost of finding later nodes.

Parallel Mapping



o Searching: Searching generally requires a single (or even partial) pass through the objects


none known.

How Current Computer Architectures Fail:

o Many searching algorithms end up depending almost entirely on random memory access latency.

Personal tools