Introduction
The GIS and Spatial domain is one of the
hottest areas of complex data right now, and an interesting case for using a graph database like Neo4j as well. There are several trends that come into play here:
- The accessibility of geographic datasets with Google Maps, the Open Street Map Project , Nokias Ovi Maps providing increasingly accurate and crowd sourced base data for geographic information
- Startups like GeoAPI and SimpleGeo providing interesting APIs for commonly needed services in an easy-to-use manner via REST and JSON
- Geographical standards and APIs like Web Map Service and others like KML, WFS etc, defined by bodies like the Open Geospatial Consortium (OpenGIS) and others catching on and becoming a good base to develop applications upon
- Most new mobile devices have now GPS sensors and APIs built in, augmenting more data with location info.
As
a result of the increasing availability of geospatial information it's
becoming part of the core domain model for an expanding range of
applications. Events, photos, running routes, logistics systems and
location games all have the geographical position of the domain data as
a core aspect of their data.
The traditional approach has
been to create spatial indexes as a separate system, typically in
PostGIS, Oracle Spatial or other specialized systems in order to then
ask them certain types of queries. Afterwards, these results are
intersected in set operations with the domain objects in question.
As
spatial attributes and queries are now becoming intertwined with the
domain models, so are the datasets. The domain objects like friends,
buildings or trucks ARE the spatial "points of interest", so a separate
spatial system just to do these queries means duplication of your data, resulting in synchronization problems. Queries like
- "Give me all my friends that are listening to the same music genre, are between 20 and 40 years old, live within 50km of my current position and are online in GTalk"
Neo4j and routing
Neo4j as a Graph Database is modeling all data as Nodes, Relationships and Properties on them. Since this is a very flexible model, arbitrary data can be added to any domain model in order to build for instance spatial indexes and logic right into the data itself. In a typical application, a subgraph could contain some road network like this:The
advantage of having the spatial data in the graph is that at any time
the different points can be related and incorporated into different
indexes, e.g. K-trees, QuadTrees and other interesting approaches.
Since Neo4j has very fast traversal performances, we can employ classic deep graph algos like the A* algorithm that is effectively a cost minimizing deep traversal through a network.
Now, in Neo4j an A* implementation in Java looks like this.
Basically, nodes are evaluated regarding their accumulated cost from
the start node, and the "as the crow flies" remaining distance to the
end node. For this, we need a EstimateEvaluator which can calculate the remaining distance (as the geodetic distance) in meters (in Ruby):
#implements a Java Interface
class GeoCostEvaluator
include EstimateEvaluator
def getCost(node, goal)
distance(node.getProperty("lat"), node.getProperty("lon"), goal.getProperty("lat"),goal.getProperty("lon"))
end
end
#calculates a geodetic distance between two spatial points
def distance(start_lat, start_lon, other_lat, other_lon)
latitude1 = start_lat.to_f * Math::PI/180 #in radian
longitude1 = start_lon.to_f * Math::PI/180 #in radian
latitude2 = other_lat.to_f * Math::PI/180 #in radian
longitude2 = other_lon.to_f * Math::PI/180 #in radian
cLa1 = Math.cos( latitude1 );
x_A = RADIUS_EARTH * cLa1 * Math.cos( longitude1 )
y_A = RADIUS_EARTH * cLa1 * Math.sin( longitude1 )
z_A = RADIUS_EARTH * Math.sin( latitude1 );
cLa2 = Math.cos( latitude2 );
x_B = RADIUS_EARTH * cLa2 * Math.cos( longitude2 )
y_B = RADIUS_EARTH * cLa2 * Math.sin( longitude2 )
z_B = RADIUS_EARTH * Math.sin( latitude2 )
#in meters
distance = Math.sqrt( ( x_A - x_B ) * ( x_A - x_B ) + ( y_A - y_B ) * ( y_A - y_B ) + ( z_A - z_B ) * ( z_A - z_B ) )
end
We also need a CostEvaluator which
calculates the cost associated with choosing a certain path using the
stored information in the graph (here the cost is attached to the
relationships representing roads as meters). In our case, we'll model
this in our domain as a "cost" property attached to the edges representing roads:
#domain model
class Road
include Neo4j::RelationshipMixin
property :cost
end
class Waypoint
include Neo4j::NodeMixin
# neo4j node properties
property :lat, :lon, :name
# lucene indexed node properties
index :name
# relationships to other waypoints
has_n(:road).to(Waypoint).relationship(Road)
# for this example just calculate the straight distance between points as cost
def connect(other)
self.road.new(other).update(:cost => distance(self.lat, self.lon, other.lat, other.lon))
end
def to_s
"Waypoint, #{name}, lon=#{lon}, lat=#{lat}"
end
end
Then, let's look up the coordinates of cities using Yahoo!'s geocoding webservice with the name and state of the city. It makes the creation of a sample a lot easier:
# create point, and look up the location via Yahoo! MapsService
def create_waypoint(city, state)
url = "http://local.yahooapis.com/MapsService/V1/geocode?appid=#{APP_ID}"
res = Net::HTTP.get(URI.parse( URI.escape(url + "&state=#{state}&city=#{city}") ))
lat = res.slice(/Latitude\>(.*)\<\/Latitude/,1)
lon = res.slice(/Longitude\>(.*)\<\/Longitude/,1)
point = Waypoint.new :name=>city, :lon=>lon, :lat=>lat
puts point
point
end
Now, populating the system with a few cities and connect them is as easy as:
# populating the routing test
Neo4j::Transaction.run do
NYC = create_waypoint('New York', 'New York')
KAN = create_waypoint('Kansas City', 'Kansas')
SFE = create_waypoint('Santa Fe', 'New Mexico')
SEA = create_waypoint('Seattle', 'Washington')
SF = create_waypoint('San Francisco', 'CA')
NYC.connect(KAN)
NYC.connect(SEA)
SEA.connect(SF)
KAN.connect(SFE)
SFE.connect(SF)
end
The resulting routing network looks something like this:
# Finding the route
sp = AStar.new( Neo4j::instance, RelationshipExpander.forTypes( DynamicRelationshipType.withName('Waypoint#road'), Direction::BOTH),
DoubleEvaluator.new("cost") , GeoCostEvaluator.new)
path = sp.findSinglePath(NYC._java_node, SF._java_node)
nodes = path.getNodes.iterator
until !nodes.hasNext() do
puts nodes.next.getProperty('name')
end
In our case, populating the network and finding a route from New York to San Francisco will look like this:
Waypoint, New York, lon=-74.007124, lat=40.714550 Waypoint, Kansas City, lon=-94.626824, lat=39.113380 Waypoint, Santa Fe, lon=-105.937406, lat=35.691543 Waypoint, Seattle, lon=-122.329439, lat=47.603560 Waypoint, San Francisco, lon=-122.420139, lat=37.779600 New York Kansas City Santa Fe San FranciscoWhich is depicted here:
This is a very trivial example, but the A* algorithm works well in Neo4j with routes hundreds and thousands of hops deep, on millions of roads and waypoints, imported for instance from OpenStreetMaps. A Neo4j plugin to the Osmosis project to export that data is underway and will be part of another spatial blog entry.
Summary
The
A* algorithm is not the best of solutions for advanced routing in real
life conditions, but it provides a first measure of the mechanics and
performance characteristics involved when operating on big graphs with
deep traversals. Of course, obvious improvements are:
- Introduce a bi-directional approach (two A* starting from start and end node, meeting in the middle), thus cutting time
- Introduce "via" waypoints like cities or big traffic hubs, cutting the total distance into shorter chunks that can be calculated in parallel
- introduce higher-order graphs that describe the logistics backbone like Highways and Autobahns and first find the nearest connection to that network, go near the end point and return to the local road network for the final distance
- Introduce better cost functions that take into account not only distance but also allowed speed, road conditions, one-way lanes etc.
- Factor in customer context like the current used car, family preferences and so on.
Still being able to do these calculations in sub-second speeds on graphs of millions of roads and waypoints makes it possible in many cases to abandon the normal approach of precomputing indexes with K/V stores and be able to put routing into the critical path with the possibility to adapt to the live conditions and build highly personalized and dynamic spatial services.
The full source code and project setup is found at github.com/neo4j-examples/ruby-astar-routing. Play with the code, add cities, connections and have some fun with the routing! There is even a Java version at http://github.com/neo4j-examples/java-astar-routing.
Feel free to comment or contact me at peter at neotechnology dot com. You're welcome to the Neo4j mailing lists as well.
