Mapping notes

[nicola]

The notes at the very end are not that good

---

Maps

Prior reading:

- maps on ipfs notes: ipfs/notes#142

• 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)

• We build a grid
• we store the points in the grid
• we store them in a quad tree (so we have a simple way to get the data out)

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

• Cut map into tiles and render each tile
• e.g. From user viewport, select all the visible tiles and render them

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

• solved problem

Route planner

Aim is to construct shortest path in a graph

1. 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)
2. 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

• New kind of solved problem

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

[daviddias]

Video will be referenced on - #22