%md
# [SDS-2.x, Scalable Data Engineering Science](https://lamastex.github.io/scalable-data-science/sds/2/x/)

This is part of [*Project MEP: Meme Evolution Programme*](http://lamastex.org/lmse/mep) and supported by databricks academic partners program.

# Map-matching Noisy Spatial Trajectories of Vehicles to Roadways in Open Street Map

## Dillon George, Dan Lilja and Raazesh Sainudiin

```
Copyright 2016-2019 Dillon George, Dan Lilja and Raazesh Sainudiin

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
```

%md

This is the precursor 2016 presentation by Dillon George as part of *Scalable Data Science from Middle Earth* student project.

[![sds/uji/studentProjects/01_DillonGeorge/038_UberMapMatchingAndVisualization](http://img.youtube.com/vi/0wKxVfeBQBc/0.jpg)](https://www.youtube.com/watch?v=0wKxVfeBQBc?rel=0&autoplay=1&modestbranding=1&start=5931&end=8274)

Here we are updating it to more recent versions of the needed libraries.

%md 
## What is map-matching?
Map matching is the problem of how to match recorded geographic coordinates to a logical model of the real world, typically using some form of Geographic Information System. See [https://en.wikipedia.org/wiki/Map_matching](https://en.wikipedia.org/wiki/Map_matching).

//This allows easy embedding of publicly available information into any other notebook
//when viewing in git-book just ignore this block - you may have to manually chase the URL in frameIt("URL").
//Example usage:
// displayHTML(frameIt("https://en.wikipedia.org/wiki/Latent_Dirichlet_allocation#Topics_in_LDA",250))
def frameIt( u:String, h:Int ) : String = {
      """<iframe 
 src=""""+ u+""""
 width="95%" height="""" + h + """"
 sandbox>
  <p>
    <a href="http://spark.apache.org/docs/latest/index.html">
      Fallback link for browsers that, unlikely, don't support frames
    </a>
  </p>
</iframe>"""
   }
displayHTML(frameIt("https://en.wikipedia.org/wiki/Map_matching",600))

%md
## Why are we interested in map-matching?

Mainly because we can naturally deal with noise in raw GPS trajectories of entities moving along *mapped ways*, such as, vehicles, pedestrians or cyclists.  

* Trajectories from sources like Uber are typically noisy and we will map-match such trajectories in this worksheet.
* Often, such trajectories lead to significant *graph-dimensionality* reduction as you will see below.  
* More importantly, map-matching is a natural first step towards learning distributions over historical trajectories of an entity.
* Moreover, a set of map-matched trajectories (with additional work using kNN operations) can be turned into a graphX graph that can be vertex-programmed and joined with other graphX representations of the map itself.

%md
## How are we map-matching?

We are using `graphHopper` for this for now. See [https://en.wikipedia.org/wiki/GraphHopper](https://en.wikipedia.org/wiki/GraphHopper).

displayHTML(frameIt("https://en.wikipedia.org/wiki/GraphHopper",600))

%md
### The following alternatives need exploration:
* BMW's barefoot on OSM (with Spark integration)
  * [https://github.com/bmwcarit/barefoot](https://github.com/bmwcarit/barefoot)
  * [http://www.bmw-carit.com/blog/barefoot-release-an-open-source-java-library-for-map-matching-with-openstreetmap/](http://www.bmw-carit.com/blog/barefoot-release-an-open-source-java-library-for-map-matching-with-openstreetmap/) which seems to use a Hidden Markov Model from Microsoft Research.
    

%md
# Steps in this worksheet

%md
### The basic steps are the following:
1. Preliminaries: 0. Attach needed libraries, load osm data and initialize graphhopper 
  - the two steps 0.1 and 0.2 need to be done only once per cluster
2. Setting up leaflet for visualisation
3. Load table of Uber Data from earlier analysis. Then convert to an RDD for mapmatching
4. Start Map Matching
5. Display Results of a map-matched trajectory

%md 
## 1. Preliminaries

%md 
### Loading required libraries
1. Launch a cluster using spark 2.4.3 (this is for compatibility with magellan built from the forked repos; see first notebook in this folder!).
2. Attach following libraries if you have not already done so:
  * map_matching - `com.graphhopper:map-matching:0.6.0` (more recent libraries may work but are note tested yet!)
  * magellan - import custom-built jar by downloading locally from `https://github.com/lamastex/scalable-data-science/blob/master/custom-builds/jars/magellan/forks/` and then uploading to databricks
  * If needed only (this is already in databricks): spray-json `io.spray:spray-json_2.11:1.3.4`

%md 
### Do Step 0 at the bottom of the notebook
#### Only once in shard per OSM file (ignore this step the second time!):
* follow section below on **Step 0.1: Loading our OSM Data ** 
* follow section below on **Step 0.2: Initialising GraphHopper**

%md

**NOTE**

If you loaded a smaller map so as to be able to analyze in the community edition, then you need the bounding box of this map to filter those trajectories that fall within this smaller map.

For example `SanfranciscoSmall` OSM map has the following bounding box:

- `-122.449,37.747` and `-122.397,37.772`

Let's put them in Scala `val`s as follows:

%md
## 2. Setting up leaflet and visualisation


## 2.1 Setting up leaflet 

You need to go to the following URL and set-up access-token in map-box to use leaflet independently:

 - https://leafletjs.com/examples/quick-start/
 - Request access-token:
   - https://account.mapbox.com/auth/signin/?route-to=%22/access-tokens/%22

%md
## 2.2 Visualising with leaflet
Take an array of Strings in 'GeoJson' format, then insert this into a prebuild html string that contains all the code neccesary to display these features using Leaflet.
The resulting html can be displayed in databricks using the `displayHTML` function.

See http://leafletjs.com/examples/geojson.html for a detailed example of using GeoJson with Leaflet.

%md 
## 3. Load Uber Data as in earlier analysis. 

Then convert to an RDD for mapmatching

%md
The number of trajectory points that are not within our bounding box of the OSM is:

%md
We will consider a trip to be invalid when it contains less that two data points, as this is required by Graph Hopper. First identify the all trips that are valid.

%md
Next is to join this list of valid Ids with the original data set, only the entries for those trips contained in `uberCountsFiltered`.

%md 
Now seeing how many data points were dropped:

%md 
Graphopper considers a trip to be a sequence of (latitude, longitude, time) tuples. First the relevant columns are selected from the DataFrame, and then the rows are mapped to key-value pairs with the tripId as the key. After this is done the `reduceByKey` step merges all the (lat, lon, time) arrays for each key (trip Id) so that there is one entry for each trip id containing all the relevant data points.

%md 
## 4. Start Map Matching

%md 
Now stepping into GraphHopper land we first define some utility functions for interfacing with the GraphHopper map matching library.
Attaching the following artefact:
- `com.graphhopper:map-matching:0.6.0`

%md 
This function takes a `MatchResult` from graphhopper and converts it into an Array of `LON,LAT` points.