Workshop Details

This talk will present a simple but very effective improvement to a variant of the classical shortest-path algorithm, a cornerstone in computer science.

The fastest-path (or minimal travel time) query between two points in a very large road map is an increasingly important primitive in modern transportation and navigation systems, thus very efficient computation of these paths on detailed road maps under dynamic traffic conditions is critical for system performance and throughput. We present a method to compute an effective admissible heuristic for the fastest path travel time between two points on a road map, which can be used to significantly accelerate the classical A* algorithm when computing fastest paths in road maps. Our method is based on two hierarchical sets of separators of the map represented by two binary trees. A preprocessing step computes a short vector of values per road junction based on the separator trees, which is then stored with the map and used to efficiently compute the heuristic at the online query stage. We demonstrate experimentally that this method scales well to maps at the continental level, providing a better quality heuristic, thus more efficient A* search, for fastest path queries between points at all distances, relative to other known heuristics.

Joint work with Renjie Chen - Max-Planck Institute for Informatics, Saarbrücken, Germany.

Every field has data.  We use data to discover new knowledge, to interpret the world, to make decisions, and even to predict the future.  The recent convergence of big data, cloud computing, and novel machine learning algorithms and statistical methods is causing an explosive interest in data science and its applicability to all fields.  This convergence has already enabled the automation of some tasks that better human performance.  The novel capabilities we derive from data science will drive our cars, treat disease, and keep us safe.  At the same time, such capabilities risk leading to biased, inappropriate, or unintended action. The design of data science solutions requires both excellence in the fundamentals of the field and expertise to develop applications which meet human challenges without creating even greater risk.

The Data Science Institute at Columbia University promotes “Data for Good”: using data to address societal challenges and bringing humanistic perspectives as—not after—new science and technology is invented.  Started in 2012, the Institute is now a university-level institute representing over 300 affiliated faculty from 12 different schools across campus.  Data science literally touches every corner of the university.

In this talk, I will present the mission of the Institute and highlights of our educational and research activities.