[postgis-users] Space partitioning index for points

[Bryce L Nordgren]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20100702/5f34f7ea/attachment.html>