lossy index

[P Kishor]

"fuzzy index" sounds like a more apt phrase than "lossy index" given
Steve's description.


On 9/9/07, Ed McNierney <ed at topozone.com> wrote:
> Crystal -
>
> Steve's description is very good; while the GiST index is extremely helpful, it is not "deterministic" (I'm sure there's a fancy database term that's more accurate) like other indexes.  What's being indexed is NOT the geometry itself, but the bounding box of the geometry, so it's not the same as indexing the actual data like you would with a text or numeric field.
>
> For all cases there the actual geometry of object A intersects the actual geometry of B, their bounding boxes will also intersect, so the query (A && B) will all objects that actually intersect.  It will also, however, return objects which do NOT intersect themselves, but whose bounding boxes intersect - think of two diagonal parallel line segments.  The test INTERSECTS(A, B) is a much more time-consuming operation than the VERY fast (A && B) test, so it is much faster to use (A && B) followed by INTERSECTS(A, B) in that order.  The first test will be executed first and will discard all objects whose bounding boxes do not intersect.  This is a "trivial rejection" test, quickly tossing out the objects that can't possibly intersect.  The more complex INTERSECTS(A, B) test is then performed only on the subset of objects that passes the first test, and will toss out any false positives where the bounding boxes intersect but the objects themselves do not.
>
>      - Ed
>
> Ed McNierney
> Chief Mapmaker
> Demand Media / TopoZone.com
> 73 Princeton Street, Suite 305
> North Chelmsford, MA 01863
> Phone: 978-251-4242, Fax: 978-251-1396
> ed at topozone.com
>
>
>
> -----Original Message-----
> From: UMN MapServer Users List [mailto:MAPSERVER-USERS at LISTS.UMN.EDU] On Behalf Of Stephen Woodbridge
> Sent: Sunday, September 09, 2007 2:36 PM
> To: MAPSERVER-USERS at LISTS.UMN.EDU
> Subject: Re: [UMN_MAPSERVER-USERS] lossy index
>
> Crystal Li wrote:
> > Hi All,
> >
> > Would any one explain lossy indexes for me? in PostGIS Manual it talked
> > about GiST indexes are assumed to be lossy.Thanks.
> >
> > Crystal
>
> I believe that this relates to the fact the gist indexes are based on
> the bbox of the geometry, so that they loose the precise nature of the
> geometry in favor of the faster bbox representation.
>
> So the use of gist indexes is  a && b means that a might interact with b
> and a moer precide test is needed to confirm that. So you see typical
> queries doing:
>
>    where a && b and intersects(a,b)
>
> HTH,
>    -Steve
>


-- 
Puneet Kishor
http://punkish.eidesis.org/
Nelson Institute for Environmental Studies
http://www.nelson.wisc.edu/
Open Source Geospatial Foundation (OSGeo)
http://www.osgeo.org/
Summer 2007 S&T Policy Fellow, The National Academies
http://www.nas.edu/