Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable

Understand

There has been significant recent interest in parallel graph processing due to the need to quickly analyze the large graphs available today.

• Many graph codes have been designed for distributed memory or external memory.
• However, today even the largest publicly-available real-world graph (the Hyperlink Web graph with over 3.5 billion vertices and 128 billion edges) can fit in the memory of a single commodity multicore server.
• Nevertheless, most experimental work in the literature report results on much smaller graphs, and the ones for the Hyperlink graph use distributed or external memory.