View Full Document

Scale-invariant random spatial networks



View the full content.
View Full Document
View Full Document

4 views

Unformatted text preview:

Background SIRSNs Scale invariant random spatial networks David Aldous September 8 2010 David Aldous Scale invariant random spatial networks Background SIRSNs Actual content is math theory inventing and studying a slightly new class of random process an abstraction of road networks Axiomatic setup Math examples particular processes within the class Consequences properties of such processes Realism Framing the topic How does your car GPS device find routes Online road maps routes differ from paper maps in 2 ways that influence the way we set up the model end of talk reflections upon data vs specific models vs classes of process David Aldous Scale invariant random spatial networks Background SIRSNs How your car GPS device finds routes You type street address 100 million in U S Recognized as between two street intersections U S road network represented as a graph on about 15 million street intersections vertices Want to compute the shortest route between two vertices Neither of the following two extremes is practical pre compute and store the routes for all possible pairs or use a classical Dijkstra style algorithm for a given pair without any preprocessing Key idea there is a set of about 10 000 intersections transit nodes with the property that unless the start and destination points are close the shortest route goes via some transit node near the start and some transit node near the destination Bast Funke Sanders Schultes 2007 Science paper and patent Given such a set one can pre compute shortest routes and route lengths between each pair of transit nodes then answer a query by using the classical algorithm to calculate the route lengths from starting and from destination point to each nearby transit node and finally minimizing over pairs of such transit nodes Takes 0 1 sec David Aldous Scale invariant random spatial networks Background SIRSNs Could regard this key fact 10 000 transit nodes such that as merely an empirical property of real network And in some



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Scale-invariant random spatial networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Scale-invariant random spatial networks and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?