Samet and Graduate Student Peng Win Best Demo Paper Award at ACM SIGSPATIAL
Hanan Samet (foreground in photo), a Distinguished University Professor of computer science and a member of UMIACS, and Shangfu Peng (background), a fifth-year computer science doctoral student, received the Best Demo Paper Award at the 2016 ACM SIGSPATIAL GIS conference held last month in San Francisco, California.
SIGSPATIAL GIS provides a forum for original research contributions covering all conceptual, design and implementation aspects of geospatial data, ranging from applications, user interfaces and visualization to data storage, query processing, and indexing.
The paper by Samet and Peng, “CDO: Extremely High-Throughput Road Distance Computations on City Road Networks,” presents a novel approach to computing a spatial analytic query as quickly as possible.
The authors note that the browsing of spatial data is becoming increasingly important. Some types of spatial queries, termed spatial analytic queries, can potentially involve thousands to millions of road network distance computations.
Examples of such analyses include complex scenarios such as how to assign 10,000 packages for delivery in a city; how much traffic congestion could be reduced if a new bridge was built; where to locate the next supermarket among a number of potential locations taking into account a variety of factors like demography, distance to a warehouse, distance to the potential customer, etc.; identifying bottlenecks in a road network for evacuation planning; and more.
They all require the computation of distance, which Samet and Peng achieve by using approximate precomputed values and table lookup instead of time-consuming shortest path computations.
Samet and Peng focus on throughput—how to compute a spatial analytic query as quickly and efficiently as possible—which depends on the error in the distance that can be tolerated. Their paper demonstrates a solution, called City Distance Oracles (CDO), using a previously developed algorithm, to achieve as many as seven million shortest distance computations per second per computer on a city road network. In contrast, most existing solutions achieve less than 5,000 shortest distance computations per second per computer.
Peng, who is advised by Samet, was lead author on the paper, which elicited interest from attendees representing Google, Apple, Uber and Lyft, for whom distance computation is important in estimating the time needed when using their services.
In addition to the best paper award, Samet and Peng—along with Samet’s other computer science doctoral students Hong Wei and Hao Li—tied for third place in the fifth annual GISCUP, a geographic information system (GIS)-focused algorithm competition co-located with the SIGSPATIAL GIS conference.
This year’s contest, sponsored by NVIDIA and Microsoft Research, focused on applying spatial statistics to spatio-temporal big data in order to identify statistically significant hot spots using a distributed computing framework and functional programming languages.
Each team was charged with utilizing a very large collection of spatio-temporal observational data—the New York City Taxi and Limousine Commission Yellow Cab trip data. The dataset consisted of over one billion records representing all Yellow Cab taxi trips in New York City between January 2009 and June 2015. Each record in the dataset contained key information such as pickup and drop-off date, time, location (latitude, longitude), trip distance, passenger count and fare amount.
Given a certain subset of this dataset, each team needed to identify the 50 most statistically significant drop-off locations by passenger count in both time and space using the Getis-Ord statistic.
Samet and his team were recognized with a certificate, GPU card and a cash award.
—Story by Melissa Brachfeld