Improve graph performance

[oscarlorentzon]

The performance for building the graph is currently bad in areas where there is high node density. The problem has many reasons, the most important one being that tiles are loaded with too many nodes, the nodes contain too much data and the tiles contains all the sequences for all the nodes in the tile. The sequences are retrieved for every tile, i.e. duplicates that are not needed are retrieved for adjacent tiles. The tiles can therefor be vary large which requires good network connection for fast retrieval. The aim of this issue is to completely rebuild the graph implementation to make it fast and dynamic.

To resolve the performance issue, the graph implementation needs to be completely rewritten. When doing this a number of other points should be addressed as well. The new implementation should be written in a way that supports the following:

• Uncaching of nodes (image, mesh, edges). ➕ Separate issue, supported Uncache images and mesh if not used #25
• Uncaching of tiles (public API on graph service to enable a cleaning component to track the graph and clean unused tiles). Uncaching a tile should flow down to cleaning of graph nodes, edges and node images and meshes. ➕ Separate issue, supported Uncache tiles when not in use #131
• Uncaching of graph nodes. ➕ Separate issue, supported Uncache tiles when not in use #131
• Uncaching should be based on geohash tiles as well as sequences ➕ Separate issue, supported Uncache tiles when not in use #131
• Usage of Falcor API ✔️
• Different graph modes (spatial, sequence) ➕ Separate issue, supported Add sequence mode to Mapillary #67
• Node filtering (separate issue but graph should be prepared for it) ➕ Separate issue, supported Filtering functionality for graph #192
• Reset edges of graph (required for filtering to only navigate to filtered nodes) ✔️
• Dynamic tile sizes and edge calculation thresholds to be able to scale the graph calculation depending on node density in area ➕ Separate issue, supported Change tile size dynamically when level 7 tiles contain too many nodes #211
• Node class should have an API for requesting a higher resolution image than the current one and emit the new image when finished ➕ Separate issue, supported Store higher resolution images in node cache #212
• Error handling and retry when API calls fails ✔️
• Unit and performance tests ➕ Separate issue, supported Implement a performance test suite #213
• Node should not have a worthy property, should be handled in graph ✔️
• Sequences of nodes should always be expected in edge calculation, a node sequence should never be null ✔️
• All methods and classes should be documented ✔️

The idea of the new graph implementation is for data to flow in the following way:

                key 
                 |
                 |
                 v
              imByKey (Core + Spatial + H) ------> Node
                / \                                 |
               /   \                                |
              v     v                               v
           imsByH  seqByKey           Image + Mesh + Core + Spatial
           (Core)   |                               |
              |     |                               |
              |     |                               v
              v     |                          Put on state 
        imsByKey    |                         (i.e. display)
  (bbox, Spatial)   |
              |   / |
              |  /  |
              | /   |
              v     v
   Spatial edges   Sequence edges
               \   /
                \ /
                 v
               Node
                / \                            
               /   \ 
              v     v
           Display arrows

In this way the node could potentially be put on the state once the node assets (image, mesh) have arrived but before the edges have been calculated. The lightweight tiles would not contain heavy node or sequence data and be fast to retrieve. The spatial edge calculation would rely on the heavy data but it would only be retrieved for exactly the image keys that are needed. The rbush spatial index will be used for determining what keys need to be turned in nodes by fetching the heavy node data. The sequence edge calculation would need to fetch the sequences for the nodes that requires edge calculation only. Falcor will be used to cache as well as batch load requests.

The implementation of the new graph issue includes:

• Data flow through observables from GraphService, Graph, Node and Edges
• Falcor API usage for building graph
• Ligthweight tile fetching
• Heavy imByKey fetching for areas required for edge calculation
• Two data streams for edge calculation (spatial, sequence)
• Changed graph, node, state and navigation implementations.

This issue requires breaking changes to the public API, therefor the library version needs to be pushed to 2.0 when implemented.

[oscarlorentzon]

The implementation of this issue should resolve #25, #67 and #131.

[oscarlorentzon]

#192 depends on the implementation of this issue.

[oscarlorentzon]

mapillary/mapillary_issues#2257 depends on the implementation of this issue.

[oscarlorentzon]

#25, #67 and #131 have not been implemented in the scope of this issue but the graph implementation supports all scenarios in those issues.

[gyllen]

@oscarlorentzon you wanna close this issue and open a new one with remaining tasks?

[oscarlorentzon]

Graph implemented according to diagram above. Separate issues created for remaingin functionality from description.