The notes at the very end are not that good

Maps

Prior reading:

Google: big queries on static datasets
need to build a big index that can be stored in a giant database
we can store this on IPFS so that users can query this statically
Components of which we need to build indeces for:
tile renderer (draws the tiles)
geo coder
- takes lat/long -> place
- takes place -> lat/long
route planner (driving directions)
How do we build these blocks on IPFS?
IPFS programming model: Authenticated Functional Data Structures
- Authenticated:
- Functional:
- Object Oriented Programming: pointer machine model gives 4 basic operation (Create Read Update Delete)
- in functional data structures we only have CR (no UD)
- sufficient for static dataset (put the data on IPFS and do query)
  Tile rendering

Storing (solved)

Rendering (solved, there are plenty of out of the box tools leaflet, mapgl)

Status

solved problem, implemented on IPFS by @davidar (leaflet)
we need to optimise it
leaflet does not implement efficient incremental updates
Geo-coder
Lat/long -> place mapping
- can be done using kd-tree
Place -> lat/long
- can be done with a Binary-Search-Tree
  k-d tree digression
Problem: we want to find the nearest neighboor of a point efficiently
For each two points in the map you can draw perpendicolar points that divide the space
- We get a voronoi diagram
- Often used in higher dimension (but also in 2d)
- We want to find the nearest neighboor in 3d (our planet is a ~sphere!)
How do we do nearest neighbor on a sphere? kd-tree
- Split the space in regions, number the nodes

The great thing about IPFS is that it gives you this data structure that you dont have to think about the lower level aspects

Status

Aim is to construct shortest path in a graph

OSM -> transit graph
- There are datasets that have some annotations
- We can use it to build Transit graphs (transit times & so on) - solved problem (see THOR)
Search
- Naive algorithm: Dijkstra algorithm? No way, too much data to crawl
- Less naive: A* (= Dijkstra + Heuristics) if we do the path distance estimation fast, then routing is very fast
  - Eucledian distance
  - Landmarks (cities & so on)
  - 2-Hop Hub labeling (exact distance in constant time between nodes in O(n) space and 1 round trip)
  - we could modify A* to cut the number of roundtrips that A* has to do
  - cannot be built incrementally - but can be built
  - consumes a lot of ram
  - we need to buy a 1TB RAM computer
  - Conceptually we calculate the square root of a distance matrix
  - For each vertex, we compute 2 label set
    - v_in, v_out, each of these labelset are collections of vertifices plus sets
    - store a list of nodes and distances
    - property of nodes: any shortest path has at least 1 vertex in v_in and v_out
  - we intersect the distance from A->B, becomes the intersection of two sorted lists

Build label set in linear time

use a grid algorithm, we sort indeces in some order (we label nodes from most high way like to least)
after taking a vertex, we add it to all hu (?)
load all map into ram (?)

Status

Questions:

can you parallelize building the index?
- Theorietically: not really, practically: you probably dont want to.
- can do speculative parallelization but prob will end up wrong.
how often do you rebuild the index?
- every time the map changes
can you change it locally only? not clear. maybe there is a way, current approach does not.
- would be AWESOME if we can make it incremental
what about other approaches?
- (like THOR) they're not performant. 2-hop hub labelling scheme is fastest
can anything do this routing? (small computers)
- yes, just dump the index into a trie into ipfs
potentially look at how ML algorithms parallelize
start with one city