[postgis-devel] KNN and Semantics

[maplabs at light42.com]

What I got out of this so far... 

* only bboxes are available (from the indexes) at execution time, and,

the box of a point is a point.. so point to point distance is a non-issue

* the query geometry is supplied in its entirety

* the idea then is to take a reasonable approach to non-point geometries
using only their bbox

  -Brian

On Mon, 26 Sep 2011 13:25:14 -0700, Paul Ramsey
  wrote:
KNNGist walks the index tree to provide ordered results. 
> Great. 
> But it's walking the tree, so the results have to be based on boxes. 
> In the case of points, the box == the point, so the ambiguity collapses. 
> In the case of everything else, it does not. 
>
> So, when someone does
>
> select * from mytable order by geom <-> 'polygon()'::geometry;
>
> what should they get back to provide the minimum surprise? Because
> they *will* get back results that differ from
>
> select * from mytable order by distance(geom, 'polygon()'::geometry);
>
> sometimes substantially. 
>
> P. 
>
> On Mon, Sep 26, 2011 at 1:19 PM, Paragon Corporation <lr at pcorp.us> wrote:
> >
> >> So, here's the deal, the KNN search works exclusively against
> >> the index. So, it only has boxes available to make decisions
> >> (not entirely true, it actually has the full geometry of the
> >> query key, but not of the index keys). That means it can
> >> return an exact answer for point-on-point queries, but for
> >> everything else it'll be a box approximation. So the n-nearest-boxes. 
> >>
> >> There are lots of ways to attack the problem... we can do
> >> pure nearest-boxes. We could also convert all the boxes to
> >> points, and do nearest-centroids. This might be easiest to
> >> explain, potentially. The trouble is, we're going to be
> >> returning an approximation for everything except points, so
> >> the question is (in my mind) which approximation is easiest
> >> to visualize and work with?
> >>
> >
> > Not sure I understand your question Paul?   I don't see how nearest
> > centroids helps much when you are talking
> > about largish polygons.  I was thinking this would just make the ST_Expand
> > like stuff faster? Oh perhaps I misunderstood that. 
> >
> > Thanks,
> > Regina
> >
> >
> >
> > _______________________________________________
> > postgis-devel mailing list
> > postgis-devel at postgis.refractions.net
> > http://postgis.refractions.net/mailman/listinfo/postgis-devel
> >
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>
>