Opened 11 years ago

Closed 9 years ago

#2452 closed enhancement (fixed)

KNN Gist for geography

Reported by: robe Owned by: strk
Priority: medium Milestone: PostGIS 2.2.0
Component: postgis Version: 2.0.x
Keywords: Cc:


A lot of people mistakenly think KNN gist exists for geography and are saddened when I tell them the bad news.

Feel free to shoot this down as a no-go Paul. I'm not sure what's involved with providing KNN gist for geography.

Change History (6)

comment:1 by pramsey, 11 years ago

It's a verrrry iffy proposition. KNN works by calculating the distances between the index keys. for 2d, those keys are in the same "space" as the objects they proxy for, but even there things get confusing as the boxes have to proxy for non-box things like lines/polygons.

Now, go into sphere-land. The objects are points/line/polygons traced on a sphere. The *keys* are three-space boxes in geocentric space that contain those objects. So, as with lines/polys in 2d space, the sort distance between the keys is *similar* to the real sort distance between the objects, it is not the *same*, and it's even harder to visualize and explain.

And for points, it's not exact either, since a KNN search would ideally put objects in their order relative to their spherical distance, the KNN sort on points would return objects based on their geocentric distances from one another.

I'll leave it to you to decide if this is a "no way". It'll never return exact correct results, for *any* geometry type, only approximations.

comment:2 by robe, 11 years ago

Iffy sounds like an iffy "no way". Would this option be better than doing

SELECT ... ORDER BY a.geom_4326 <-> b.geom_4326

If not then I guess not worth the effort. The never return exact results doesn't bother me so much since for most cases, people use this as a first hope anyway and not the final. Anyway probably something to vote on rather than do blindly.

comment:3 by pramsey, 9 years ago

Owner: changed from pramsey to strk

This got done by strk, unless I miss my guess. It'll still be really iffy w/o recheck, but for points it should work fine. Good luck explaining the non-point behaviour to mere mortals.

comment:4 by strk, 9 years ago

Me ? KNN ? Is something wrong with trac times ? This ticket is documented as being created 21 months ago. In no way I touched KNN more than 4 months ago (and I did the index assisted n-dimensional KNN). Paul, I think KNN was yours ?

comment:5 by pramsey, 9 years ago

Ah, well you did the hard parts of it then, since the geography index is just the n-dimensional index using 3 dimensions.

comment:6 by pramsey, 9 years ago

Resolution: fixed
Status: newclosed

This got done at #2703

Note: See TracTickets for help on using tickets.