{"64246":{"#nid":"64246","#data":{"type":"event","title":"CSE Seminar: Daniel Delling","body":[{"value":"\u003Cp\u003EWe present a novel algorithm to solve the nonnegative single-source \nshortest path problem on road networks and other graphs with low highway\n dimension. After a quick preprocessing phase, we can compute all \ndistances from a given source in the graph with essentially a linear \nsweep over all vertices. Because this sweep is independent of the \nsource, we are able to reorder vertices in advance to exploit locality. \nMoreover, our algorithm takes advantage of features of modern CPU \narchitectures, such as SSE and multi-core. Compared to Dijkstra\u0027s \nalgorithm, our method makes fewer operations, has better locality, and \nis better able to exploit parallelism at multi-core and instruction \nlevels. We gain additional speedup when implementing our algorithm on a \nGPU, where our algorithm is up to three orders of magnitude faster than \nDijkstra\u0027s algorithm on a high-end CPU. This makes applications based on\n all-pairs shortest-paths practical for continental-sized road networks.\n The applications include, for example, computing graph diameter, exact \narc flags, and centrality measures such as exact reaches or \nbetweenness.Joint work with Andrew Goldberg, Andreas Nowatzyk, and \nRenato Werneck.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"PHAST: Hardware-Accelerated Shortest Path Trees"}],"uid":"27330","created_gmt":"2011-02-15 10:11:07","changed_gmt":"2016-10-08 01:54:09","author":"Della Phinisee","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-02-25T13:00:00-05:00","event_time_end":"2011-02-25T14:30:00-05:00","event_time_end_last":"2011-02-25T14:30:00-05:00","gmt_time_start":"2011-02-25 18:00:00","gmt_time_end":"2011-02-25 19:30:00","gmt_time_end_last":"2011-02-25 19:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"37041","name":"Computational Science and Engineering"},{"id":"47223","name":"College of Computing"},{"id":"50877","name":"School of Computational Science and Engineering"}],"categories":[],"keywords":[{"id":"11917","name":"Daniel Delling"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDella Phinisee, \u003Ca href=\u0022mailto:della@cc.gatech.edu\u0022\u003Edella@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}