[postgis-users] Space partitioning index for points

[Paul Ramsey]

GeoHash doesn't cut it? It's space partitioned, just not as balanced
as a kd-tree, but for points... no? I'll look up my info on the GiST
work that was done, but note that it didn't make it into 9.0, but into
9.1, and as I recall Oleg and co did not seem to think the kd
implementation was going to be very effective.

P

On Thu, Jul 1, 2010 at 5:20 PM, Bryce L Nordgren <bnordgren at fs.fed.us> wrote:
>
> Greetings postgis-ers,
>
> We have a need to rapidly sift through a pile of points, and the Rtree
> implementation is slower than our timelines will allow. We are exploring
> mutliple pathways to enhancing our performance, including creating a indexed
> geohash column with ST_geohash(). "Ok", but not "great".
>
> However, there are tantilizing references in the mailing list to improved
> performance for points using space partitioning schemes. In particular, I
> refer to Paul Ramsay's message of a year ago, where he said:
>
> Nearest neighbor, as Stephen notes in the followup is not something
> that is necessarily easy in general. However! Another development
> on-stream for PostgreSQL 8.5 will allow us to both (a) use k-d tree
> indexes for points, which are much more efficient and (b) to do
> nearest-neighbor searching using the index tree, which will be a great
> deal more optimal for general cases.
>
> (http://www.mail-archive.com/postgis-users@postgis.refractions.net/msg08026.html)
>
> I now note that PostgreSQL 8.5 and PostGIS 1.5 have been released, so I
> would like to follow up on this topic to see if k-d trees have in fact been
> implemented, or, if not, how one might start such an approach (perhaps a
> topic for the dev list).
>
> Thanks,
> Bryce
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>
>