Introduction
Every location-based service [1 ] has to solve the following problem: find all venues within a given distance from the current location of the user. Long before the advent of mobile devices, geographic information systems (GIS) [2 ] had to deal with this (and other) problem(s).
The NoSQL [3 ] datastore MongoDB [4 ] supports geospatial queries [5 ] (i.e. queries based on coordinates) out of the box. For a better understanding of the things to come, I recommend reading this article on Spring Data Mongo DB for an introduction to both MongoDB and the corresponding Spring Data API.
Planar Maps
Let’s start with a simple example consisting of four points in a plane. The meaning of the units of the coordinate systems can be whatever you choose: miles, kilometers etc.
Let’s insert these points into a collection named location:
1C:\dev\bin\mongodb-2.0.2\bin>mongo 2MongoDB shell version: 2.0.2 3connecting to: test 4> db.createCollection("location") 5{ "ok" : 1 } 6> db.location.save( {_id: "A", position: [0.001, -0.002]} ) 7> db.location.save( {_id: "B", position: [1.0, 1.0]} ) 8> db.location.save( {_id: "C", position: [0.5, 0.5]} ) 9> db.location.save( {_id: "D", position: [-0.5, -0.5]} )
To enable geospatial indexing, we set an appropriate index on the position array:
1> db.location.ensureIndex( {position: "2d"} )
That’s it. Now we can perform queries like this (blue circle, red box from the above image) using special MongoDB operators:
1> db.location.find( {position: { $near: [0,0], $maxDistance: 0.75 } } ) 2{ "_id" : "A", "position" : [ 0.001, -0.002 ] } 3{ "_id" : "D", "position" : [ -0.5, -0.5 ] } 4{ "_id" : "C", "position" : [ 0.5, 0.5 ] } 5> db.location.find( {position: { $within: { $box: [ [0.25, 0.25], [1.0,1.0] ] } } } ) 6{ "_id" : "C", "position" : [ 0.5, 0.5 ] } 7{ "_id" : "B", "position" : [ 1, 1 ] }
Try this with your relational database without defining custom types and functions!
Spring Data MongoDB API
With Spring Data MongoDB the same queries can be implemented with very few lines of code. First of all, we define a POJO representing a location on the map:
1public class Location {
2
3 @Id private String id;
4
5 private double[] position;
6 ...
7}
A repository defining the queries may look like this:
1public interface LocationRepository extends MongoRepository<Location, String> { 2 3 List<Location> findByPositionWithin(Circle c); 4 5 List<Location> findByPositionWithin(Box b); 6}
Spring Data derives the appropriate implementation at runtime from these interface methods. The classes Circle, Point and Box are abstractions belonging to the MongoDB API.
1public class MongoDBGeoSpatialTest { 2 3 @Autowired LocationRepository repo; 4 5 @Autowired MongoTemplate template; 6 7 @Before public void setUp() { 8 // ensure geospatial index 9 template.indexOps(Location.class).ensureIndex( new GeospatialIndex("position") ); 10 // prepare data 11 repo.save( new Location("A", 0.001, -0.002) ); 12 repo.save( new Location("B", 1, 1) ); 13 repo.save( new Location("C", 0.5, 0.5) ); 14 repo.save( new Location("D", -0.5, -0.5) ); 15 } 16 17 @Test public void shouldFindAroundOrigin() { 18 // when 19 List<Location> locations = repo.findByPositionWithin( new Circle(0,0, 0.75) ); 20 21 // then 22 assertLocations( locations, "A", "C", "D" ); 23 } 24 25 @Test public void shouldFindWithinBox() { 26 // when 27 List<Location> locations = repo.findByPositionWithin( new Box( new Point(0.25, 0.25), new Point(1,1)) ); 28 29 // then 30 assertLocations( locations, "B", "C" ); 31 } 32 ...
Our query results with the Spring Data MongoDB API are the same as with the mongo console:
1Circle: 2A(0.001, -0.002) 3D(-0.500, -0.500) 4C(0.500, 0.500) 5 6Box: 7C(0.500, 0.500) 8B(1.000, 1.000)
The full source code of this example can be found at github . A good starting point is mongodb.MongoDBGeoSpatialTest.
Performance considerations
MongoDB does a really good job when indexing geospatial data. I did a small test comparing queries with circle and box shapes. I expected the box query to be faster than the circle query (because checking a box requires only comparison of the coordinates, checking a circle requires calculating distances) – but it wasn’t! My test scenario was the following:
- Create 100,000 random locations with coordinates in
(-1,1) x (-1,1) - Perform queries around 10,000 different random center points
(x,y)with coordinates also in(-1,1) x (-1,1)using- a circle with center
(x,y)and radiusr = 0.1 - a box with center
(x,y)andwidth = sqrt(pi) * r(thus having the same area as the circle)
- a circle with center
These are the test results:
| Circle | Box | |
|---|---|---|
| Average time per query [ms] | 47.6592 | 47.2629 |
| Average hits per query | 750 | 749 |
It shows there are no differences at all. Of course, this is no proof – but a hint. Also the box is good approximation of the circle – at least it covers roughly the same amount of lcations (which are probably not the same though). But with MongoDB the box trick is not needed at all!
If you want check this yourself have a look a this unit test for details: mongodb.MongoDBMassTest.
Spherical Maps
Since the earth is a spherical globe [6 ] (and not a flat plane), working with planar maps is only a good approximation when you are dealing with small distances. Besides that you usually use latitude and longitude coordinates to describe a point on the globe and distances are measured in miles or kilometers. The earth is not a perfect globe, so the distance between two arcdegrees of longitude also varies [7 ].
MongoDB honors these facts since version 1.8 and provides special operators to support the spherical model. By default the range for geospatial index covers the interval [-180, 180) since latitude and longitude are expressed with these values. A coordinate tupel in MongoDB consists of [longitude, latitude]. Order is important.
I will use the Spring Data API alone, since it automagically scales down to miles or kilometers. In a raw MongoDB example you have to scale by yourself. Our example is based on three German cities:
| City | Longitude | Latitude |
|---|---|---|
| Berlin | 13.405838 | 52.531261 |
| Cologne | 6.921272 | 50.960157 |
| Düsseldorf | 6.810036 | 51.224088 |
I extracted the coordinates with the help of Google Maps [8 ]. We only have to add a single(!) line of code to our repository:
1List<Location> findByPositionNear(Point p, Distance d);
Since Düsseldorf and Cologne are not that far away from each other, the following query …
1List<Location> locations = repo.findByPositionNear(DUS , new Distance(70, Metrics.KILOMETERS) );
… finds the two cities of Cologne and Düsseldorf. Important is the use of the Metrics enum. Using KILOMETERS or MILES does two things under the hood:
- it switches to spherical query mode
- it applies appropriate scaling to the distance value
If we stretch our search a little bit more …
1List<Location> locations = repo.findByPositionNear(DUS , new Distance(350, Metrics.MILES) );
… all three cities are found. These examples can be found at github too.
Summary
I showed you how easy geospatial data and queries are handled by MongoDB. With the help of Spring Data MongoDB this ease is carried over to the Java world. We worked with simple planar maps, did a rough performance analysis and also looked at the more real world spherical model.
Spring Data Project
These are my other posts covering the Spring Data project:
Part 1: Spring Data Commons
Part 2: Spring Data JPA
Part 3: Spring Data Mongo DB
Expect upcoming blog posts on Spring Data Neo4j and Spring GemFire
References
[1] Location-based service
[2] GIS – Geograhic information system
[3] NoSQL databases
[4] MongoDB
[5] MongoDB – Geospatial Indexing
[6] Projections and Coordinate Systems
[7] Geographical Distance
[8] Finding longitude and latitude on Google Maps
Was this post helpful?
More articles
fromTobias Trelle
17.12.2018 Your job at codecentric?
Jobs
Agile Developer und Consultant (w/d/m)
Alle Standorte
More articles in this subject area
Discover exciting further topics and let the codecentric world inspire you.
Gemeinsam bessere Projekte umsetzen.
Wir helfen deinem Unternehmen.
Du stehst vor einer großen IT-Herausforderung? Wir sorgen für eine maßgeschneiderte Unterstützung. Informiere dich jetzt.
Hilf uns, noch besser zu werden.
Wir sind immer auf der Suche nach neuen Talenten. Auch für dich ist die passende Stelle dabei.
Blog author
Tobias Trelle
Software Architect
Do you still have questions? Just send me a message.
Do you still have questions? Just send me a message.