BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20101117T170000Z
DTEND:20101117T173000Z
LOCATION:393
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: Processing large graphs is becoming increasingly important for many domains such as social networks, bioinformatics, etc. Unfortunately, many algorithms and implementations do not scale with increasing  graph sizes. As a result, researchers have attempted to  meet the growing data  demands using parallel and  external memory techniques. =0A=0AWe present a novel asynchronous approach to compute Breadth-First-Search (BFS), Single-Source-Shortest-Paths, and Connected Components  for large graphs in shared memory.  Our highly  parallel asynchronous approach hides data latency  due  to both poor  locality  and delays  in  the underlying  graph data storage. We present an experimental study applying our technique to  both  In-Memory and Semi-External Memory graphs utilizing multi-core processors and solid-state memory devices. Our experiments using synthetic and real-world datasets show that our asynchronous approach is able to overcome  data  latencies  and  provide  significant  speedup  over  alternative approaches. For example, on billion vertex graphs our asynchronous BFS scales up to 14x on 16-cores.
SUMMARY:Multithreaded Asynchronous Graph Traversal for In-Memory and Semi-External Memory
PRIORITY:3
END:VEVENT
END:VCALENDAR