What's the best way to do geo radius by distance search?

Questions / Help
1

What would be the optimal way to have a set of locations in the database, and enable search of addresses by distance.

i.e. All addresses within a 10 mile radius, etc

I have the longitude and latitude of every address in the db.

Is there a good dep for this, or is better to go the postgis route?

2

What it amounts to, is to check which latitudes and longtitudes are inside a given box.

Is there a good dep that does this for you? Not that I know of right now.

However, building this yourself should be rather straightforward:

The algorithm to compare two-dimensional (or even n-dimensional) is very widely used and quite simple to understand. In most cases, using PostGIS is not required (depending on how much data you have; it probably has the same algorithms but with an implementation that compiles to bare metal).

You have a circle (cx, cy, cr) and a list of points (each with a px, py). You can check for each of these points in O(n) (linear time) if they are in the circle using the squared euclidean distance: ((cx - px)² + (cy - py)² < cr²)

First thing to note here is that we don’t perform a square root each time, which greatly improves the speed of the algorithm (we’re only interested in if it is inside the radius, not what the actual distance is). Obviously, cr² can be precomputed outside of the iteration.

However, it can be further sped up (by a constant factor) by comparing each point with a bounding box instead of a bounding circle, since the algorithm then becomes:

bx1 = cx - cr
bx2 = cr + cr
by1 = cy - cr
by2 = cy + cr
for each point:
       px > bx1 && px < bx2
&&  py > by1 && py < by2

After checking if it is inside the box, you can still filter on only the things inside the circle (But for many implementations, it is actually not a problem if locations inside a box instead of a circle are picked and then you can leave this extra step of complexity out).

If you don’t have that much data, you’re now done.
If you do have much data, you can go one step further and store your points in a so-called Quadtree or K-d tree. This is what e.g. PostGIS also uses internally. These trees allow you to find all close points in O(log n) (logarithmic time).

1 Like
3

It is better to go postgis route :slight_smile:

3 Likes
4

I’ve heard from some friends that do this sort of thing that postgis is really great.

2 Likes
5

I have actually done this in the recent past. If you are already using postresql there is no reason not to use postgis. Just make sure that you have an index on the location column.

CREATE TABLE addresses(address VARCHAR, location GEOGRAPHY);

CREATE INDEX ON addresses USING GIST (location);

SELECT * FROM addresses WHERE ST_DWithin(location, ST_SetSRID(ST_Point(longitude::decimal, latitude::decimal),4326)::geography, 10 * 1000); -- searches for addresses with 10KM

If postgresql isn’t fast enough for you, you can use redis too.

The below cmd gives the first address within 10km

Redix.command(:redis, ~w(GEORADIUS addresses #{lng} #{lat} 10000 m WITHDIST COUNT 1))
3 Likes
6

Thank you for all the answers, much appreciated.

Very interesting to see that Redis has GEORADIUS.

For now I opted for Postgre extensions - Earthdistance and Cube and using this Ecto query:

def in_area do
Member
|> Ecto.Query.where([m], fragment(“earth_box(ll_to_earth(33.5916433, -117.6986604), 563) @> ll_to_earth(?, ?)”, m.latitude, m.longitude))
|> Repo.all
end

I am going to try Redis though to see if there is a perceivable speed difference.

Thank you again for your suggestions.

1 Like
7

Redis ‘might’ be faster on the super simple queries, but when you get more complex (Like all restaurants that serve burgers under a certain price inside a certain radius ordered by rating) then PostgreSQL is what you will want for certain.

1 Like