Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I am looking for a way to do fast KNN queries on a dataset of 10+ million 3D points (and growing). I was hoping PostGIS would do the trick with its new <-> and <#> operators, but they don't seem to work in three dimensions. Does anyone know any workarounds that would extend the KNN GiST index to 3D? Right now I'm using a "normal" spatial index with the &&& operator, but that creates all the issues that led to the addition of the KNN index in the first place.

share|improve this question

2 Answers 2

up vote 0 down vote accepted

A "patch that introduces kNN search for cubes with euclidean, taxicab and chebyshev distances" was recently offered on the pgsql-hackers list.

Note that the cube type, a PostgreSQL extension, can be used to represent points or cubes in n-dimensions (n up to 100 by default, more if that limit is removed), so this patch should among other things enable 3D point search.

I haven't yet used it, and note that one of the replies suggests it may currently break some regression tests. But, it seems to add the necessary <-> operator and "OPERATOR CLASS gist_cube_ops" changes for a gist index on cube distances to work.

share|improve this answer

I know a bit late to reply to this, but PostGIS 2.2 for PostgreSQL 9.5, just recently committed <<->> operator which is a KNN distance for 3D. For 9.5 it returns true 3d distance, for 9.4 and below, just uses 3D bounding box centroid (so would work fine for points).

Details here:

http://postgis.net/docs/manual-dev/geometry_distance_centroid_nd.html

I still need to update the docs, but to utilize the index part, need a 3D index which you create like

CREATE INDEX idx_sometable_geom_nd_gist ON sometable USING gist(geom gist_geometry_ops_nd);
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.