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.


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:


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);
| improve this answer | |
  • BTW PostGIS 2.2.0 is out. Windows 64-bit builds for 9.3-95 are on stackbuilder. Other packagers have started building packages for it. – LR1234567 Oct 16 '15 at 22:30

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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