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).
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);
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.