0

Suppose I have a database storing 1000000 geolocations of different users in a city. It will be painful for the server to execute the command SearchNearbyUsers(myLocation, 50) if I use a list or array to hold all the geolocations and compare the distances one by one.

The server is coded in C# with Web API 2. Is there any library designed for doing such calculations with geolocations?

If there is not any library available, what data structure should be used in order to make this calculation easier? I have looked at R-tree before, but to be honest, I do not understand the logic clearly and it seems to be quite complex.

This is what the geolocation class looks like:

public class GeoLocation
{
    public float latitude { get; set; }
    public float longitude { get; set; }
}

Both the latitude and longitude are sent by clients. Values are obtained via navigator.geolocation.getCurrentPosition().

S.C.
  • 900
  • 1
  • 13
  • 39
  • If you are using a database system like MongoDB or MySQL, it can do the work for you, you'll just have to set it up first. For MySQL, read carefully this chapter : http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html. Otherwise (and I hope you have a good reason not to), R-trees _are_ the way to go, you'll have to study them ! – Rerito Nov 26 '14 at 11:00

4 Answers4

3

Usually those spatial operations are done using spatial indexes. The R-Tress is just one complex example of this, but you may get simpler ones also. Just divide your whole area to smaller pieces (e.g. rectangles) and search within those areas that fit share their index with the given coordinate. So I propose to enable spatial indexes on your server and then use a spatial library such as GDAL.

So if you have a coord (4,5) you first have a look at all rectangles intersecting a buffer of witdh x around your point. And now you just search within all geometries that are located within those rectangles.

EDIT: On SQL Server you may also use its spatial extension in order to retrieve those nearby features (see here). Basically create a buffer around your input-geometry using STBuffer and than perform an intersect on that buffer. Using the described spatial index those operations are quite fast.

MakePeaceGreatAgain
  • 35,491
  • 6
  • 60
  • 111
  • What if the two users are in fact really close to each other but lying in different spatial blocks? – S.C. Nov 26 '14 at 09:07
  • 1
    @AldourCheng, R-trees are designed to avoid this kind of problem ... The query mechanism will guarantee you will find every object (stored in the tree) in a given spatial area. They are usually the core of spatial indexes in DB systems :) – Rerito Nov 26 '14 at 10:19
  • 1
    That´s why I wrote have a look at the rectangles that intersect the buffer. So you´d get up to four rectangles for a single point (which is still much less then searching the whole area). – MakePeaceGreatAgain Nov 26 '14 at 10:20
2

if you are a beginner and want to avoid the use of trees ...

  1. create grid map of your supported area

    • just a simple 2D cell grid
    • cell grid
    • each cell has its coordinates i,j or index ix=i+j*ni where ni is number of cells per i axis
    • so for each point you can simply compute the cell ownership
    • make a list of points per each cell
    • something like:
    • Vector<int> map[nj][ni];
    • and fill the list with point index inside the cell ...

  2. comparison

    • compute user cell location
    • and compare only points in that cell and in 8 neighbouring ones ...
    • the more dense the cell grid the more speed you have
    • if your cell is smaller then the comparison range then compare also more neighbours
    • to cover whole range safely
    • enter image description here
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • What if all the geolocation data is initially stored in a database but not in a dictionary defined in code? – S.C. Nov 26 '14 at 10:54
  • @AldourCheng you can simply write a for loop going through all points and fill the map with point indexes prior to implement this to add/del point routines... – Spektre Nov 26 '14 at 10:55
  • @AldourCheng the only significant drawback is that deletion of point needs to update all point indexes bigger then the deleted one by decrementing it by one... in all cells. but that can be avoided by adding _deleted flag in point list ... – Spektre Nov 26 '14 at 10:58
1

If you are using a data store like Mongo, geospatial querying is pretty easy and quite nice. Here are the Docs

You could try looking into something like this. It is what I habe used for a client to download location relevant data in a recent project, and it works a dream.

EDIT For finding locations in the real world with Lat and Long, to get the correct result when querying with distances, you must use a spherical index

This Question will help you out with the near query using the mongo c# driver.

Edit 2 After learning about you using MS SQL, here are some useful links to go along with one Phillip provided in another answer.

Query Spatial Data For Nearest Neighbour
Spatial Data

Community
  • 1
  • 1
David Watts
  • 2,249
  • 22
  • 33
  • Does it apply on MS SQL server? – S.C. Nov 26 '14 at 09:41
  • Sadly not, MongoDB is a database in its own right. Are you solidly tied into MS SQL? You are giving yourself a handicap working with geospatial queries using MS SQL. Mongo isn't even the only option. There are plenty of Databases out there with much better support for geospatial queries than MS SQL – David Watts Nov 26 '14 at 09:45
  • Thanks for the info. It seems that MS SQL is now adding more functionalities for handling spatial data. I am referring to the link posted by PhillipH. – S.C. Nov 26 '14 at 09:49
  • There is more information out there. I'll update my answer with some more links. – David Watts Nov 26 '14 at 10:20
1

Well, If you are storing your data in SQL Server you'd use a Spatial Index http://msdn.microsoft.com/en-us/library/bb934196.aspx.

PhillipH
  • 6,182
  • 1
  • 15
  • 25