Beliebte Suchanfragen

Cloud Native

DevOps

IT-Security

Agile Methoden

Java

|
//

Spring Data – Part 4: Geospatial Queries with MongoDB

15.3.2012 | 6 minutes of reading time

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:

  1. Create 100,000 random locations with coordinates in (-1,1) x (-1,1)
  2. 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 radius r = 0.1
    • a box with center (x,y) and width = sqrt(pi) * r (thus having the same area as the circle)

These are the test results:

CircleBox
Average time per query [ms]47.659247.2629
Average hits per query750749

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:

CityLongitudeLatitude
Berlin13.40583852.531261
Cologne6.92127250.960157
Düsseldorf6.81003651.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

|

share post

Likes

0

//

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.