When it comes to algorithms, our people take the lead both in and out of the office

Bo Xu, a Sr. Researcher at HERE CTO, has been named to the organizing committee for this year’s ACM SigSpatial Cup. We spoke with Bo to learn more about the prestigious competition, his involvement, and how he brings that expertise to his work at HERE.

Each year, the ACM SIGSPATIAL (Association for Computing Machinery - Special Interest Group on Spatial Information) annual conference presents the GIS (Geographic Information Systems) Cup. Beyond being a mouthful of acronyms, it’s a competitive event that draws the attention of teams of algorithm developers across the world.

Bo Xu has been involved with the SigSpatial annual conferences for the last 18 years, and he’s been selected as one of three leaders that will evaluate the competitive entries for 2018. Dr. Xu has vast professional experience in spatial algorithms, which includes journal papers published on TSAS and GeoInformatica. He is an established researcher on spatial problem solving both inside HERE, and in the greater geo-spatial programing industry. We asked him about how his work at HERE and in the industry relate.

“SIGSpatial is highly relevant to our work. We build maps, we build location intelligence, all of this is about GIS and spatial information. Particularly in my group, we do a lot of work in spatial algorithms and with probe data.”

In the GIS Cup, competitors are challenged to develop an algorithm that solves a specific, well defined problem. Entries are then evaluated by having the algorithm analyze and process the test data.

This year’s contest will focus on analyzing large spatial networks in order to find upstream nodes for a given pair of source node and destination node. An upstream node is a node that is on a path from the source node to the destination that does not have any loops.

The identification of upstream nodes is an important problem in critical infrastructure analysis for locating assets that are crucial to a nation’s economy, security, and health. An example is identifying transformers that supply electricity to a water pump that is needed by the sole hospital in a region.

Another example is identifying the road segments that may be affected by a traffic accident while the induced congestion spreads over time; the analysis results in this case may be used to improve route planning for vehicles to avoid the congestion on the way toward their destinations. As Dr. Xu explains.

“The evaluation of the algorithms should be objective. Your code is going to generate a result, and we can evaluate that result against what we know is the truth from the test data – so in that sense, it’s about efficacy, efficiency and accuracy.

One of the areas that Dr. Xu and his colleagues in HERE Research are working on is using algorithms to analyze and evaluate probe data. This is a painstaking process of using extremely large datasets made up of simple, individual pieces of information – in this case, the information comes in the form of GPS coordinates.

“Our probe data is mostly GPS locations that you collect from vehicles, from pedestrians, from taxis – those are the kinds of resources we have. So, our company uses probe data to get real time traffic information to make our map update faster – to automatically update the map based on the probe data we receive.”

Of course, HERE receives probe data from millions of cars and sources every day. Developing algorithms that process that data effectively creates a result that can’t be matched by human effort. But more importantly, that result uses the collective of data points to recognize changes in the world and update accordingly.

“We are developing techniques to automatically detect traffic accidents in real-time from probe data streams. The challenge is to distinguish not only between congestion caused by rush hour traffic and unexpected congestion, but also between congestion caused by local disturbances and that caused by car collisions. The difference is sometimes subtle, and the algorithm has to look at various factors of traffic conditions upstream and downstream of the source location of the congestion. We are building machine learning models to recognize the traffic condition signatures of accidents.

“More than traffic, we are detecting points of interest, and determining the status of points of interest. Like the case of if we have a gas station in our database. Looking at the data, if we find that we don’t have a lot of vehicles stopping in that location, then probably that gas station is closed.

“Also, we can use this approach to identify new points of interest from the probe data. We look at what we call ‘clustering’. If you look at the probe data, for maybe the past 6 months; by clustering, you find the areas where there is a high density of probe points. We can then compare this location with our existing database of points of interest, then we can move to the next step of verifying what is happening in that point.”

Using algorithms to evaluate data can go beyond identifying points of interest. By extension, those same GPS data points can be used to identify changes in road geometry, from subtractions like lane closures, to additions where the data indicates there are completely new roads needing to be mapped.

We’re incredibly proud to have Bo Xu on our team, and we’ll be following his process in evaluating the GIS Cup through the winners announcement coming in November. Want to have your go at creating an efficient algorithm for a specific cause? Visit ACM SIGSPATIAL to learn how to get involved.