<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Sun, Jun 15, 2014 at 1:23 AM, Åsmund Tokheim <span dir="ltr"><<a href="mailto:asmundto@gmail.com" target="_blank">asmundto@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">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.</div>
</blockquote><div><br></div><div>Sorry, but I fail to see such case - if point is close, it will be also close on at least one of 3 planes (x,y), (x,z), (y,z) <br><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div>Speaking about performance, are you aware that your query probably doesn't make use of any spatial index?</div></div></blockquote><div><br></div><div>It does. Tested.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div>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.</div>

</div></blockquote><div><br></div><div>As far as I was able to test, "select * from table order by st_3ddistance(geometry, '') limit 20" doesn't  use index.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div>My best attempt at an optimized 3d kNN-search would be something like:</div><div>1. Select all points within some reasonable bbox</div><div>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.</div>

<div>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.</div></div></blockquote><div><br></div>
<div>We thought about it, but deciding what is reasonable box might be complicated. And in my approach, I'm merely getting 3x number of rows from 3 different indexes, and it was (in my tests) VERY fast.<br><br></div><div>
depesz <br></div></div></div></div>