Past Meetup

Simon Peyton Jones: "Getting from A to B: fast route-finding on slow computers"

This Meetup is past

98 people went

uSwitch

The Cooperage, 5 Copper Row, London, SE1 2LH · London

How to find us

Enter Copper Row pedonal path and the stairs leading to the ZPG sign.

Location image of event venue

Details

Simon Peyton Jones (https://www.microsoft.com/en-us/research/people/simonpj/) presents: "Getting from A to B: fast route-finding using slow computers", a talk inspired by "Computing the shortest path: A* search meets graph theory (https://www.microsoft.com/en-us/research/wp-content/uploads/2004/07/tr-2004-24.pdf)" paper (Andrew V Goldberg and Chris Harrelson).

[WARNING] Unfortunately, because of building and safety regulations, we are forced to a max number of 100 people in the room. Please be aware that we will be forced to leave people out if we reach that number. I'm really sorry for this drastic decision but there is no way to predict how many people will show up.

Abstract

We all now take it for granted that online maps will rapidly display a fast route from A to B. But these maps are gigantic: a map of Europe has 20 million intersections and 40 million road segments. How can a computer find the shortest path in such a large map, without examining all those intersections and roads?

This is a classic graph problem, known as the Shortest Path problem, with solutions that date back to 1960. But in the last couple of decades there has been significant progress that dramatically speeds up the solution.

In this talk I'll explain both the old solutions and the new cool ideas. I hope you'll go away with a clear example of how some clever computer science can take a problem that previously required a big, fast computer, and make it fast enough to run on a slow, mobile device.

Meetup

PapersWeLove (http://paperswelove.org) London proudly brings to you the best papers every month! Please join us to read and discuss the most amazing ideas in computer science. We are meeting at uSwitch - ZPG (https://www.uswitch.com/about-us/contact-us/) offices near Tower Bridge (https://goo.gl/maps/qJXZek4fMNU2) with the following schedule:

• 6.30pm: networking, pizza and drinks.

• 7:00pm: presentation starts

The Speaker

Simon Peyton Jones (https://en.wikipedia.org/wiki/Simon_Peyton_Jones), MA, MBCS, CEng, graduated from Trinity College Cambridge in 1980. Simon was a key contributor to the design of the now-standard functional language Haskell, and is the lead designer of the widely-used Glasgow Haskell Compiler (GHC). He has written two textbooks about the implementation of functional languages.

After two years in industry, he spent seven years as a lecturer at University College London, and nine years as a professor at Glasgow University before moving to Microsoft Research (Cambridge) in 1998.

His main research interest is in functional programming languages, their implementation, and their application. He has led a succession of research projects focused around the design and implementation of production-quality functional-language systems for both uniprocessors and parallel machines.

More generally, he is interested in language design, rich type systems, software component architectures, compiler technology, code generation, runtime systems, virtual machines, and garbage collection. He is particularly motivated by direct use of principled theory to practical language design and implementation -- that's one reason he loves functional programming so much.