Neo4j Spatial: Finding Things Close to Other Things


Geography is a natural domain for graphs and graph databases.

So natural, in fact, that early map users of Neo4j simply rolled their own map support. However, it takes some effort to deal with spatial indexes, geometries and topologies, and so, since September 2010, the Neo4j Spatial project has been providing early access releases enabling a wide range of convenient and powerful geographic capabilities in the Neo4j database.

Some of these have already been used in production projects during the last year. As we move forward and continue to refine the APIs, we will publish a series of blogs introducing users to various aspects of this powerful, yet simple, geographic processing framework: from proximity searches, through routing, to complex GIS Topology analysis.

One of the simplest and most intuitive places to start is to ask the question: How do I find things close to other things?.

This is exactly the question answered by location-based services on the web, as well as a number of existing spatial databases. In the NoSQL area, CouchDD released GeoCouch in 2009, and MongoDD released their geohashing index in 2010. Both answer exactly this question.

Unlike these other NoSQL databases, Neo4j started with support for complex geometries in 2010. While simple proximity searches have been possible, they have only recently become simple and intuitive.

A Neo4j Spatial Example


In this example, I will demonstrate just how simple proximity searches have become using Neo4j Spatial.

// Initialize database
GraphDatabaseService graph = new EmbeddedGraphDatabase("db");
SpatialDatabaseService db = new SpatialDatabaseService(graph);
SimplePointLayer layer = db.createSimplePointLayer("neo-text");

// Add locations
for (Coordinate coordinate :
     makeCoordinateDataFromTextFile("NEO4J-SPATIAL.txt")) {
        layer.add(coordinate);
}

// Search for nearby locations
Coordinate myPosition = new Coordinate(13.76, 55.56);
List<SpatialDatabaseRecord> results =
    layer.findClosestPointsTo(myPosition, 10.0);
graph.shutdown();

The above code initializes the spatial index, adds a number of location points to the index and then performs a proximity query.

In fact, it does everything you need and you could just copy it into a new class’ main method and it will run. Well, almost.

You do need to get your data from somewhere, and in the above code we wrote the method makeCoordinateDataFromTextFile(). This simply returns an iterator of Coordinate objects representing the locations to add to the index.

Before getting into that, let’s start by explaining the rest of the code in a little more detail.

SimplePointLayer


The new API added for the 0.5 release of Neo4j Spatial simplifies working with point locations. Looking at the above code, we see the following steps are involved:

Initialize the SimplePointLayer

This is a map Layer, or collection of indexed points, and is created with the code:

SimplePointLayer layer = db.createSimplePointLayer("neo-text");

Neo4j Spatial works with all kinds of spatial geometries, including Points, LineString and Polygons.

For this example, since we are working with Points, we need do no more than create a SimplePointLayer to get access to Point capabilities and proximity searches. In further blog posts we will delve deeper into what a Layer really is and how to deal with much more complex data.

Adding Points

To add a single Point to the database, you could call:

layer.add(13.0, 55.6);

This will add a Point at longitude 13.0 and latitude 55.6, inside the city of Malmö, Sweden, coincidentally close to where the Neo4j core development team is.

While this is simple, internally the code will work with actual Point objects, made from Coordinate objects. And when dealing with large amounts of data, you will quite likely work with these too.

The code we used in the main example calls a method that produces an Iterator of Coordinates, and adds those to the layer:

for (Coordinate coordinate :
     makeCoordinateDataFromTextFile("NEO4J-SPATIAL.txt")) {
        layer.add(coordinate);
}

The code in makeCoordinateDataFromTextFile can be read from the unit test code in TestSimplePointLayer, and simply reads some ASCII Art from a file, and makes x and y coordinates for each pixel of the text.

The file we used contained the following:

.#       # #########   #####         #       ###               #####   ########      #     #########   #####       #     #        
## # # # # ## # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # #
# # # # # # # # # ## # # # # # # # # #
# # # ####### # # # # # ##### ### ######## ####### # # ####### #
# # # # # # # # # ## # # # # # # # #
# # # # # # ######### # # # # # # # # # #
# ## # # # # # # # # # # # # # # # #
# # ######### ##### # ### ##### # # # # ##### # # #########

When this is exposed to a mapping system, through Neo4j’s support for common GIS’s like GeoServer and uDig, we can see the text written over the south of Sweden, with the top-left corner of the N in the town of Malmö.

Learn More about the Neo4j Spatial Project


OK, this is not a real-world example, but it is certainly cool!

Proximity Search

So, the last thing to do is search for points nearby.

The following code from the main example does just that:

Coordinate myPosition = new Coordinate(13.76, 55.56);
List<SpatialDatabaseRecord> results =
    layer.findClosestPointsTo(myPosition, 10.0);

We have decided we want to know what is near the point at (13.76, 55.56) which is somewhere in the middle of this map.

Perhaps we are tourists traveling around the countryside of southern Sweden, and bored of endless fields of brilliant yellow canola flowers, we ask the map for something more relaxing to do than getting a stiff neck while sitting in the car.

We tell the map where we are:

Coordinate myPosition = new Coordinate(13.76, 55.56);

We don’t want to travel more than 10km further, so we limit the search to 10km from our position:

List<SpatialDatabaseRecord> results =
    layer.findClosestPointsTo(myPosition, 10.0);

The results we get are already sorted by distance, so we could just pick the first and go there:

Coordinate closest = results.get(0).getGeometry().getCoordinate();

However, you might be curious to see everything in the 10km search limit, so let’s pop that onto another map layer:



Yes, just what the doctor ordered!

What’s Next for Neo4j Spatial?


This example showed one specific API. But as mentioned in the beginning, this is layered on top of a much more powerful set of capabilities, like:

    • Adding spatial intelligence to existing graph database models
    • Working with more complex geometries, and performing more complex spatial queries
    • The Open Street Map graph data model and performing queries specific to OSM

One of the most important questions developers need to deal with is how to adapt their existing data to Neo4j Spatial.

The example in this blog does not show you the graph structure at all. But of course it is, in fact, creating a special graph structure to support both the points and the index, and you can access that graph using normal Neo4j APIs.

However, this is not the most useful and intuitive way to go.

What should you do if you already have your own graph, and part of the graph already represent locations? How can you adapt your model to Neo4j Spatial so that you can index your existing graph? How do you perform proximity searches and other spatial queries on your own data model?

Luckily for us, Neo4j Spatial was designed from the beginning to deal with exactly those questions.

While there is a lot of functionality in Neo4j Spatial, the different ways of exposing it (REST, Java, GeoTools, Neo4j Index API) are not set in stone. We very much welcome your feedback on how you think they should look!

Just comment on the Neo4j mailing list or directly to the author.



Want to learn more about graph databases? Click below to get your free copy of O’Reilly’s Graph Databases ebook and discover how to use graph technologies for your application today.