2

We are trying to get nearest neighbors within a user given radius. As far as I understand ST_DWithin degrades as distances are increased. The problem with using KNN is that it keeps on searching even though the radius is crossed.

For example, let's say we are searching for 3 petrol stations in 1 km. KNN keeps searching for 3 candidates and we had to filter out those outside the radius after KNN is done. This leads to unnecessary time consumption.

Is there a way that we can do nearest neighbors search within a user given radius which combines the benefit of both. Or is there an alternative better than these 2 ?

  • There is a somewhat obscure way of doing this. I will attempt to write it up when I get a moment. – John Powell Mar 28 '18 at 8:27
1

Boundless has a good article how to solve your problem:

select *
from table1, table2
where st_distance(table1.the_geom,table2.the_geom) < 1000
order by table1.the_geom <-> table2.the_geom
limit 3

From the article:

The <-> is a “distance” operator, [...] it [..] makes use of the index when it appears in the ORDER BY clause.

Notes:

  • You need spatial indexes on the_geom to perform fast !
  • <-> uses box calculations that are approximations. If you want an exact result you need to limit to a higher number, and run a sort by st_distance on the result.

Like this:

with index_query as (
  select *, st_distance(table1.the_geom,table2.the_geom) as distance
  from table1, table2
  order by table1.the_geom <-> table2.the_geom
  limit 10
)
select * from index_query where distance < 1000 order by distance limit 3;
  • KNN can timeout since it doesn't take care of radius. I will try your query but I suspect it has the same issue. – Rahul Bansal Jan 16 '17 at 12:17
  • Enabling gist index (as suggested by @RoVo) on the "the_geom" columns on both the table will help a lot with search timings. – Amitabh Kant Feb 24 '18 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.