We presented  “CDO: Extremely High-Throughput Road Distance Computations on City Road Networks (Best Demo Award)” in SIGSPATIAL 2016. We demonstrate a solution, termed City Distance Oracles (CDO), using our previously developed -distance oracle to achieve as many as 7 million shortest distance computations per second per commodity machine on a city road network, i.e., 10K × 10K origin-distance (OD) matrix can be finished in 14 seconds.

The reaction of a number of companies that make use of such spatial analytic queries was that typical queries are concentrated in a small local region rather than the whole continental region, termed the spatial concentration property. As an example of such a use-case is a delivery company that needs to plan the delivery route for each truck every day, where the route of each truck must be restricted into a local region, i.e., the region near to the package warehouse. In particular, each such warehouse handles 1, 000 to 10, 000 packages per day, and each truck can deliver a maximum of 150 packages per route. In order to efficiently assign the packages to trucks and plan routes, the delivery company computes a distance matrix that captures the distance between every pair of destination locations of the packages, This is a common spatial analytic query which makes between 1 million and 100 million distance computations. Here, the spatial concentration property means that in the general case, all destination locations of packages must be in proximity to the warehouse, say within 100KM.

Job Opportunities:

We use the LEHD dataset to obtain the job locations around the Bay Area. The workload shows the nearby job opportunities (e.g., within 10 kms) for each census block in the Bay Area, requiring 120 million distance computations, where CDO finished it within 18 seconds.