July 19, 2012

Research Lifts Cluster Weight Off Graphs

Datanami Staff

If one wanted to analyze the graph of a large social networking site such as Twitter, it would be an uphill climb without the weight of a significant cluster. And in many cases, even then, the result would not be reached for several hours.

Carlos Guestrin of Carnegie Mellon University thinks that is all about to change. Guestrin, the codirector of CMU’s Select Lab, and his team have developed GraphChi, software that stores graphs in a computer’s hard drive as opposed to its RAM. Delving into the hard drive for graph storage has apparently led to some remarkable results.

The researchers behind the project say that GraphChi can run massive graph computations on a single machine via the novel algorithm for processing the graph from disk (SSD or hard drive). Programs for GraphChi are written in similar vertex-centric model as the parent project, GraphLab.

GraphChi runs vertex-centric programs asynchronously (i.e changes written to edges are immediately visible to subsequent computation), and in parallel. GraphChi also supports streaming graph updates and changing the graph structure while computing.

According to a recent description of how some are seeking to solve graph problems, “a Mac Mini running GraphChi can analyze Twitter’s social graph from 2010—which contains 40 million users and 1.2 billion connections—in 59 minutes.” Guestrin puts that into perspective, adding, “The previous published result on this problem took 400 minutes using a cluster of about 1,000 computers.”

Typically, hard drives are slow to read and write data, making them less than ideal for handling graphs. The lynchpin of GraphChi appears to be a system designed by Aapo Kyrola which accesses the hard drive with efficiency and order. If the hard drive problem has been solved, the power of the individual computer could indeed be unleashed. “PCs don’t have enough RAM to hold an entire Web graph, but they do have hard drives, which can hold a lot of information,” says Guestrin.

This new infrastructure is hinted at but not explained in detail on GraphChi’s site. “GraphChi runs vertex-centric programs,” explains the site, “asynchronously (i.e changes written to edges are immediately visible to subsequent computation), and in parallel. GraphChi also supports streaming graph updates and changing the graph structure while computing.”

Even if GraphChi may not yet be able to handle the big data demands of the BI world, Guestrin predicts that researchers will find plenty of uses for the software, especially when it comes to cleaning large amounts of data. “A researcher in computational biology could do large-scale computations on their PC; a developer working on a data-center algorithm can test it on their laptop before pushing it to the cloud… Tools like GraphChi will let many companies and startups solve all their graph-computing needs on a single machine.”

Related Stories

Cray Puffs 70k Handout for Graph Computing Prowess

The Science of Social Sentiment

Big Data Cloud Delivers Military Intelligence to U.S. Army in Afghanistan