BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20121113T173000Z
DTEND:20121113T180000Z
LOCATION:255-EF
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: Breadth-First Search is an important kernel used by many graph-processing applications. In many of these emerging applications of BFS, such as analyzing social networks, the input graphs are low-diameter and scale-free. We present an efficient breadth-first search algorithm that is advantageous for low-diameter graphs. We adopt a hybrid approach, combining a conventional top-down algorithm along with a novel bottom-up algorithm. The bottom-up algorithm can dramatically reduce the number of edges examined, which in turn accelerates the search as a whole. On a multi-socket server, our hybrid approach demonstrates speedups of 3.3-7.8 on a range of standard synthetic graphs and speedups of 1.4-3.8 on graphs from real social networks compared to a strong baseline. We also show speedups of greater than 2.3 over the state-of-the-art multicore implementation when using the same hardware and input graphs.
SUMMARY:Direction-Optimizing Breadth-First Search
PRIORITY:3
END:VEVENT
END:VCALENDAR
BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20121113T173000Z
DTEND:20121113T180000Z
LOCATION:255-EF
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: Breadth-First Search is an important kernel used by many graph-processing applications. In many of these emerging applications of BFS, such as analyzing social networks, the input graphs are low-diameter and scale-free. We present an efficient breadth-first search algorithm that is advantageous for low-diameter graphs. We adopt a hybrid approach, combining a conventional top-down algorithm along with a novel bottom-up algorithm. The bottom-up algorithm can dramatically reduce the number of edges examined, which in turn accelerates the search as a whole. On a multi-socket server, our hybrid approach demonstrates speedups of 3.3-7.8 on a range of standard synthetic graphs and speedups of 1.4-3.8 on graphs from real social networks compared to a strong baseline. We also show speedups of greater than 2.3 over the state-of-the-art multicore implementation when using the same hardware and input graphs.
SUMMARY:Direction-Optimizing Breadth-First Search
PRIORITY:3
END:VEVENT
END:VCALENDAR