<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content="text/html; charset=us-ascii" http-equiv=Content-Type>
<META name=GENERATOR content="MSHTML 9.00.8112.16434"></HEAD>
<BODY>
<DIV dir=ltr align=left><SPAN class=227415821-26092011><FONT color=#0000ff 
size=2 face=Arial>Good point +++ for boxes.  You still might miss some but 
you are more likely to miss with centroids</FONT></SPAN></DIV><BR>
<BLOCKQUOTE 
style="BORDER-LEFT: #0000ff 2px solid; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; MARGIN-RIGHT: 0px" 
dir=ltr>
  <DIV dir=ltr lang=en-us class=OutlookMessageHeader align=left>
  <HR tabIndex=-1>
  <FONT size=2 face=Tahoma><B>From:</B> 
  postgis-devel-bounces@postgis.refractions.net 
  [mailto:postgis-devel-bounces@postgis.refractions.net] <B>On Behalf Of 
  </B>David William Bitner<BR><B>Sent:</B> Monday, September 26, 2011 5:52 
  PM<BR><B>To:</B> PostGIS Development Discussion<BR><B>Subject:</B> Re: 
  [postgis-devel] KNN and Semantics<BR></FONT><BR></DIV>
  <DIV></DIV>I don't think you actually have to deal with the magic 
number. 
  <DIV><BR></DIV>
  <DIV>Something like </DIV>
  <DIV>select * from foo where 
  st_within(st_extent(st_knnbox(geoma,geomb,10),geoma)) order by 
  st_distance(geoma,geomb) limit 10</DIV>
  <DIV><BR></DIV>
  <DIV>would still be able to use the KNN index to find the magic extent that 
  will include all the features that are possible to be in the closest 10 as 
  from the furthest extent of the 10 closest boxes will certainly include all of 
  the "actual" 10 closest.</DIV>
  <DIV><BR><BR>
  <DIV class=gmail_quote>On Mon, Sep 26, 2011 at 4:40 PM, Paul Ramsey <SPAN 
  dir=ltr><<A 
  href="mailto:pramsey@opengeo.org">pramsey@opengeo.org</A>></SPAN> 
wrote:<BR>
  <BLOCKQUOTE 
  style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" 
  class=gmail_quote>Trade-offs abound.<BR>centroid-vs-centroid has the 
    advantage of ease of understanding<BR>box-vs-box has the advantage of being 
    over-determined. you could at<BR>least theoretically do an index-assisted 
    knn pull wrapped as a<BR>subquery inside a standard st_distance test. 
    however, that goes back<BR>to magic numbers again (how many items should one 
    pull in the indexed<BR>query) so...<BR>There don't seem to be any great 
    soln's here.<BR><FONT color=#888888>P.<BR></FONT>
    <DIV>
    <DIV></DIV>
    <DIV class=h5><BR>On Mon, Sep 26, 2011 at 2:35 PM, Paragon Corporation 
    <<A href="mailto:lr@pcorp.us">lr@pcorp.us</A>> wrote:<BR>> Okay I 
    get the issue now forgot it was for order by stuff. I guess from my<BR>> 
    perspective bounding box would be better though that's not ideal 
    either.<BR>> for long linestrings which is what I'm usually dealing with 
    centroid is<BR>> useless and for small polygons the bounding box is a 
    better approximation<BR>> than centroid<BR>> for thumbnail 
    check.<BR>><BR>> It's ST_Distance BTW -- get with the program Paul. 
     Your beloved distance is<BR>> gone. No more. history vamush. 
    :)<BR>><BR>> Thanks,<BR>> Regina<BR>><BR>><BR>>> 
    -----Original Message-----<BR>>> From: <A 
    href="mailto:postgis-devel-bounces@postgis.refractions.net">postgis-devel-bounces@postgis.refractions.net</A><BR>>> 
    [mailto:<A 
    href="mailto:postgis-devel-bounces@postgis.refractions.net">postgis-devel-bounces@postgis.refractions.net</A>] 
    On<BR>>> Behalf Of Paul Ramsey<BR>>> Sent: Monday, September 26, 
    2011 4:25 PM<BR>>> To: PostGIS Development Discussion<BR>>> 
    Subject: Re: [postgis-devel] KNN and Semantics<BR>>><BR>>> 
    KNNGist walks the index tree to provide ordered results.<BR>>> 
    Great.<BR>>> But it's walking the tree, so the results have to be 
    based on boxes.<BR>>> In the case of points, the box == the point, so 
    the ambiguity<BR>>> collapses.<BR>>> In the case of everything 
    else, it does not.<BR>>><BR>>> So, when someone 
    does<BR>>><BR>>> select * from mytable order by geom <-> 
    'polygon()'::geometry;<BR>>><BR>>> what should they get back to 
    provide the minimum surprise?<BR>>> Because they *will* get back 
    results that differ from<BR>>><BR>>> select * from mytable order 
    by distance(geom, 'polygon()'::geometry);<BR>>><BR>>> sometimes 
    substantially.<BR>>><BR>>> P.<BR>>><BR>>> On Mon, 
    Sep 26, 2011 at 1:19 PM, Paragon Corporation<BR>>> <<A 
    href="mailto:lr@pcorp.us">lr@pcorp.us</A>> wrote:<BR>>> 
    ><BR>>> >> So, here's the deal, the KNN search works 
    exclusively against the<BR>>> >> index. So, it only has boxes 
    available to make decisions (not<BR>>> >> entirely true, it 
    actually has the full geometry of the query key,<BR>>> >> but 
    not of the index keys). That means it can return an<BR>>> exact 
    answer<BR>>> >> for point-on-point queries, but for everything 
    else it'll be a box<BR>>> >> approximation. So the 
    n-nearest-boxes.<BR>>> >><BR>>> >> There are lots of 
    ways to attack the problem... we can do pure<BR>>> >> 
    nearest-boxes. We could also convert all the boxes to<BR>>> points, 
    and do<BR>>> >> nearest-centroids. This might be easiest to 
    explain,<BR>>> potentially. The<BR>>> >> trouble is, we're 
    going to be returning an approximation for<BR>>> >> everything 
    except points, so the question is (in my mind) which<BR>>> >> 
    approximation is easiest to visualize and work with?<BR>>> 
    >><BR>>> ><BR>>> > Not sure I understand your 
    question Paul?   I don't see how nearest<BR>>> > centroids 
    helps much when you are talking about largish<BR>>> polygons. 
     I<BR>>> > was thinking this would just make the ST_Expand 
    like stuff<BR>>> faster? Oh<BR>>> > perhaps I misunderstood 
    that.<BR>>> ><BR>>> > Thanks,<BR>>> > 
    Regina<BR>>> ><BR>>> ><BR>>> ><BR>>> > 
    _______________________________________________<BR>>> > 
    postgis-devel mailing list<BR>>> > <A 
    href="mailto:postgis-devel@postgis.refractions.net">postgis-devel@postgis.refractions.net</A><BR>>> 
    > <A href="http://postgis.refractions.net/mailman/listinfo/postgis-devel" 
    target=_blank>http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>>> 
    ><BR>>> _______________________________________________<BR>>> 
    postgis-devel mailing list<BR>>> <A 
    href="mailto:postgis-devel@postgis.refractions.net">postgis-devel@postgis.refractions.net</A><BR>>> 
    <A href="http://postgis.refractions.net/mailman/listinfo/postgis-devel" 
    target=_blank>http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>>><BR>><BR>><BR>> 
    _______________________________________________<BR>> postgis-devel 
    mailing list<BR>> <A 
    href="mailto:postgis-devel@postgis.refractions.net">postgis-devel@postgis.refractions.net</A><BR>> 
    <A href="http://postgis.refractions.net/mailman/listinfo/postgis-devel" 
    target=_blank>http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>><BR>_______________________________________________<BR>postgis-devel 
    mailing list<BR><A 
    href="mailto:postgis-devel@postgis.refractions.net">postgis-devel@postgis.refractions.net</A><BR><A 
    href="http://postgis.refractions.net/mailman/listinfo/postgis-devel" 
    target=_blank>http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR></DIV></DIV></BLOCKQUOTE></DIV><BR><BR 
  clear=all>
  <DIV><BR></DIV>-- <BR>************************************<BR>David William 
  Bitner<BR></DIV></BLOCKQUOTE></BODY></HTML>