Integrate nearest neighbor query into public API

[daniel-j-h]

By now we have a spatial index that works on top of a z-order space filling curve

• Space filling curve based spatial index #22
• Adds a space filling curve based spatial index, closes #22 #68

and we have the (optional) functionality in the public API for users to sort graph nodes by a z-order space filling curve

• Re-number nodes: embed spatially based on space-filling curve, closes #17 #62

with the idea that it will benefit graph traversals due to better memory locality when we walk a graph e.g. during dijkstra's s-t shortest path.

---

We need to integrate the spatial index into the public API so that users can

• start and end their search at locations and not node ids
• get back a path of locations and not just node ids

Questions in terms of designing the API surface

• Should we decouple the spatial index from the graph and expose both low-level structures to the user?
• Or should we tighly couple the graph and the spatial index so that users can do graph.search(start, stop) with locations?

---

One key realization I had while building the spatial index: If we already sort graph nodes based on the z-order space filling curve, then the spatial index on the very same nodes is free! 😮 This is because all our spatial index is doing is sorting nodes by z value and then doing binary searches with search space pruning on the z values.

In practice what this could mean if we want to tighly couple graph and spatial index

1. We always sort nodes by z order space filling curve and construct the graph based on that
2. We then put the spatial index on top of it; in theory there is nothing to do in construction; in practice I believe we want to at least compute and cache the z values because they are not the cheapest to re-compute
3. When the user searches for a location in the spatial index we simply do binary search on the z values and return indices as results
4. These indices are the graph node ids to start searches from and stop searches at

What we then have to store for the graph and the spatial index

• a permutation to reverse the z value sorting to return results back to users
• one lng, lat array with one item per graph node, keyed by node id
• one z value array with one item per graph node, keyed by node id, computed from the lng, lat (purely as cache and an optimization)

We should explore if this sort of tighly coupling is worth it for the synnergy effects: graph and spatial index will be very small.

[daniel-j-h]

After ruminating a bit more on this it just came to me that the computation and caching of z values based on the longitutde and latitude locations is only needed in a few places:

1. To run the initial two binary searches here to get the range of [zmin, zmax]
2. Whenever we exit the query bounding box to compute the next z value back in the query bounding box (bigmin) and to then jump back here

The two initial binary searches are in O(log n): For a graph with 10M nodes we will check around 7 locations in the array, for a graph with 100M nodes we will check around 8 locations in the array, and so on. We could adapt our binary search implementation so that it computes these very few z values on demand when it is running.

For computing bigmin we also need the current z value. Here it depends on the query and how often we need to compute bigmin, and if it's worth it computing it on demand. There is a synnergy with the tricks to reduce bigmin computations e.g. for cases where we leave and then after 2-3 locations enter the z-curve again already. This we need to look into a bit more.