SCHEDULE: NOV 10-16, 2012
When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.
Direction-Optimizing Breadth-First Search
SESSION: Breadth First Search
EVENT TYPE: Papers, Best Student Paper Finalists
TIME: 10:30AM - 11:00AM
SESSION CHAIR: Umit Catalyurek
AUTHOR(S):Scott Beamer, Krste Asanović, David Patterson
ROOM:255-EF
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.
Chair/Author Details:
Umit Catalyurek (Chair) - Ohio State University
Scott Beamer - University of California, Berkeley
Krste Asanović - University of California, Berkeley
David Patterson - University of California, Berkeley
Click here to download .ics calendar file
Click here to download .vcs calendar file
Click here to add event to your Google Calendar
Direction-Optimizing Breadth-First Search
SESSION: Breadth First Search
EVENT TYPE: , Best Student Paper Finalists
TIME: 10:30AM - 11:00AM
SESSION CHAIR: Umit Catalyurek
AUTHOR(S):Scott Beamer, Krste Asanović, David Patterson
ROOM:255-EF
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.
Chair/Author Details:
Umit Catalyurek (Chair) - Ohio State University
Scott Beamer - University of California, Berkeley
Krste Asanović - University of California, Berkeley
David Patterson - University of California, Berkeley
Click here to download .ics calendar file