[postgis-users] Will it work, or am I overlooking something?

[Åsmund Tokheim]

Hi

As far as I can see, there are some cases where your algorithm won't
produce optimal solutions. E.g if you search for neighbours around origo,
and there are lots points with coordinates like (1, 1, 1000), (1, 1000, 1),
(1000, 1, 1), then your unions might fail include points like (5, 5, 5).
Your result could be used as an upper bound for the distance where the
optimal solution lies. By 3d-ordering all the points within a bounding box
with side-lengths 2*(your upper bound) you should have a guaranteed optimal
solution. The number of points within the bbox might (and should normally)
be much more than the number of neighbours that you are searching for, so
I'm not sure if I would recommend such a complicated approach out of
performance considerations.

Speaking about performance, are you aware that your query probably doesn't
make use of any spatial index? I think you would have to generate columns
with 2d-versions of the_point in the xy, xz and yz-planes, and index each
of those columns in order for the index to be used. This means that your
current query would probably run about 3x slower than simply using
st_3ddistance from the beginning.

My best attempt at an optimized 3d kNN-search would be something like:
1. Select all points within some reasonable bbox
2. If the number of points is k or more, then sort and return the first k
points. Otherwise restart from 1 with an expanded bbox.

It could be possible to let the expansion of the bbox in step 2 depend on
the number of points returned, but I would be careful not to have the
algorithm repeat too many times.

Hope this helps
Åsmund


On Sat, Jun 14, 2014 at 7:02 PM, hubert depesz lubaczewski <depesz at gmail.com
> wrote:

> Hi,
> I'm looking for a fast kNN search in 3d space.
>
> For simplicity sake, let's say I have table:
>
> create table test (
>     id serial primary key,
>     the_point geometry
> )
>
> the_point is always single point in 3d space: POINT(x y z).
>
> kNN gist searches can use <-> operator, but this operator doesn't handle
> 3d space.
>
> So, I wrote 3 functions, which convert 3d point to 2d points by removing
> one of dimensions:
>
> translate_xy() -> returns POINT(x y)
> translate_xz() -> returns POINT(x z)
> translate_yz() -> returns POINT(y z)
>
> Then, I create indexes (3) on translate_*( the_point ).
>
> Then, when I need to find nearest neighbors (let's say - 10), I search
> using all of above 3 indexes, union results (getting at most 3x number of
> rows), reorder using st_3ddistance(), and limit to 10.
>
> Basically the query is something along the lines of:
>
> select * from test where id in (
>     ( select id from test order by translate_xy( the_point ) <->
> translate_xy( 'POINT(50 50 50)' ) limit 10 )
>     union
>     ( select id from test order by translate_xz( the_point ) <->
> translate_xz( 'POINT(50 50 50)' ) limit 10 )
>     union
>     ( select id from test order by translate_yz( the_point ) <->
> translate_yz( 'POINT(50 50 50)' ) limit 10 )
> )
> order by st_3ddistance(the_point, translate_yz( 'POINT(50 50 50)' )
> limit 10;
>
> Is that good enough, or am I overlooking some case where it can go wrong?
>
> Regards,
>
> depesz
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at lists.osgeo.org
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20140615/5c4db735/attachment.html>