CODEWITHSUNDEEP
c#algorithmdata-structuresgeolocation
S.C.
S.C.

Reputation: 920

Implementing "Search nearby users" function on server

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().

Upvotes: 0

Views: 355

Answers (4)

Spektre
Spektre

Reputation: 51863

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

Upvotes: 2

MakePeaceGreatAgain
MakePeaceGreatAgain

Reputation: 37050

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.

Upvotes: 3

David Watts
David Watts

Reputation: 2289

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

Upvotes: 1

PhillipH
PhillipH

Reputation: 6222

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.

Upvotes: 1

Related Questions