Best way to build Spatial Search Algorithms.

I’m demonstrating that in the algorithm. We first presented this at GraphConnect 2018, and we used data from New York. So, you see Manhattan over there, we did some route finding and it worked pretty well. There were some rough edges, but I think it went quite nicely. We then a year later presented it to San Francisco and improved it. And then last year and this year, we are using Sweden.

So, I imported two weeks ago the latest Swedish OpenStreetMap data from OpenStreetMap. It’s a very large data set. And I did all of the preparatory work to get the routine graph prepared. And the preparation of the reading graph, you can find out more by watching the GraphConnect 2018 talk. What it ends up with, is a possibility to follow route relationships, as you see on the screen here. And the simplest possible way to do that in cipher is with the shortest path function, which is a function built into cipher.

So, the cipher query, like the one you see over there on the left, has to match statements to find the two places you’re interested in. In this case, I’m looking at a restaurant called Mia Maria’s, which is right across the street from the Neo4j office in Molma, and another office called Farsi which is right across town from Neo4j. And I look for the shortest path between the two of these. The consequence when I do this in the demo, and I can show you, is a rather strange path. And that looks a little odd.

It seems to be going out into the Docklands, and then it goes off and does this big loop around Malmö. The reason for that, it isn’t actually correct. This is not an ideal path. The shortest path function in cipher is always going to look for the shortest number of hops. It is a graph-only concept. It’s not weighted. Furthermore, it doesn’t consider distance. So, highways will be made of very long line segments that will take a long time, even if you’re driving fast. And that’s why I chose the highway because it was fewer hops.

If instead, we use a different algorithm, I’ll now change a day. See the highlighted part on the left there, I’ve just changed it to call the Dijkstra algorithm. And I’ve told it, “Yes, follow the rich relationships, but weighted by distance.” That means it’s going to find the shortest path by distance. And you end up with what you see on the right, a much, much better path. So, this is a massive optimization. It makes it much, much more useful. I want to say a little more about weighted paths before we get to the demo. First, you need to prepare your graph so that you do have these properties on the relationships.

We had to calculate the distances between every single intersection, and store it on the graph in advance to make a route and graph. Now, a professional product that does readings is going to do a lot more than just calculate distances. It’s going to model a speed. The speed, not just what the speed limit is but perhaps a live speed traffic conditions, a lot of other things. But you need to at least start with something like this. And then, of course, you can find that the shortest path by their total weight and total distance.

Now, there are two weighted shortest path algorithms available in the app library that we use for the demo. One is day Dijkstra, which is a mono-directional breadth-first search. And the other one, A, is a lot faster because you give it a second function. You don’t only have the function defining the weight for the path length, you also have a function defining a kind of preferred direction. And that will go a lot faster. For the data sets we’re working in, we don’t see an obvious difference. So, A is useful when you deal with very much more complicated data sets. So, as I mentioned before, we’ve downloaded this before. I’m going to switch to the demo and show you exactly how this works in our app.

I have a demo over here, which shows Sweden. And if I zoom in for a moment here, you’ll see I’ve already done some shortest path calculations. This is where our office is. Let’s get rid of some of the selections here and get it back. So, the way the shortest part works, is you need to select points of interest. For example, that one, which is right across the street from our office. And then, you will of course find the point to… Let me just take away these selections here. Right. So I’m going to, as I did in that presentation, find something quite far away from the office down here for example, and exactly as we saw, we got an awful path that doesn’t look good at all.

It’s following the highway and it’s definitely not the shortest path. There must be a shorter route. So, on the left, I have the choice of algorithm. I’m going to switch it to Dijkstra, and we’ll see that gives a much much, much faster route to take. What we can also do is search larger areas. But what I want to show you as well, I mentioned before the preparation of the data. To do this, we need to have created a graph that can be routed across. So, there is a feature in this app for demonstrating the routine graph. It’s going to slow them up down a little. There we go. So, this is a debug option that I’ve turned on and it’s important to remember that OpenStreetMap will have points along the way for every bend in the road. It needs to be able to draw the map.

So, it’s optimized for being able to draw them out. But when you want to do routing, you don’t care about that. If you have a long wiggly road, you don’t care about rooting over 100 points. You just want to know the relationship from the intersection point, a place where you might make a decision, to another intersection point and the total distance. So, what I’ve displayed on the map right now is the written graph that we overlaid on top of OpenStreetMap. We read some procedures that will crawl the OpenStreetMap graph, find intersection points, find the points of interest, and it’s then going to connect them in a simplified graph that is optimized for routing. And there are two aspects to this graph. One is the relationship between intersections, and the other one is how do you get from a restaurant to the street?

So if I zoom in on some area over here, you’ll see what we’ve done for that. These little green lines are the special relationships we’ve added between points that were free-floating on the map. Like this one here says Graffiti Café. So, Graffiti Café was not connected to the graph, how can you route if you’re not connected to the graph? Well, we calculated the closest street and then we calculated the point on that street, interpolated because quite often there wasn’t an existing point. Add a point to the graph, go to the relationship in there, and connect all the points of interest into a fully-routable graph.

Let’s move on to another part of the demo. So, I’m going to zoom out and show you polygons. What I started with, is I went to something like this. This is the actual OpenStreetMap’s own view. And in OpenStreetMap, you can investigate the underlying layers. And I searched for objects that were considered to be provincial boundaries. And when I found them, I could select them and get a view like this on the left. You don’t need to worry about the details. But what it has done is shown me that I’ve correctly found the administrative boundary of the province of Skåne in Southern Sweden. And so once I recognize that I can then say this is useful for the polygon algorithms.

So, I just recorded this into the app. And if I click on Skåne and enable showing polygons, there you see the provincial boundary of Skåne. I also incidentally found only the land area. So, there is just the land area. So, you can do quite a lot by investigating OpenStreetMap, and that’s very rich. Spend enough time and you’ll find a lot of things. But what I’ve put into this map is simply the identities of all of the provinces, so that I can, for example, click in a few areas like this and it will search for. So I had a cipher equation, cipher query. When I click on the map, it passes that point to the database and says, find a province that contains this point using the algorithm point in a polygon which I will describe in a bit more detail. So that was very, very useful.

Leave a Comment