nearest neighbor search from xyz coordinates

[Andreas Jochem]

Hello,

I have a table containing x y z coordinates. But I have no geometry column?
Is it possible to find the k nearest neighbors of any point. Is there
something like a kd-tree Index in postgres???

I know, if i had a geometry column I could make use of the distance
function to find the k nearest neighbors. But my table has millions of
records, thus it would take a very long time to use the distance
function for each point.

Thanks in advance.

Andi

[Serge Fonville]

What exactly do you want to measure, since values can be compared easily by
a where clauseIf you would want for example all rows within a spherical
distance
you will either have to write a stored procedure (which takes 4 parameters
x,y,z,distance)
Or manually compare each corodinate to the distance

Regards,

Serge Fonville

Post by Andreas Jochem
Hello,
I have a table containing x y z coordinates. But I have no geometry column?
Is it possible to find the k nearest neighbors of any point. Is there
something like a kd-tree Index in postgres???
I know, if i had a geometry column I could make use of the distance
function to find the k nearest neighbors. But my table has millions of
records, thus it would take a very long time to use the distance function
for each point.
Thanks in advance.
Andi
--
http://www.postgresql.org/mailpref/pgsql-general

[Angel Alvarez]

Post by Andreas Jochem
Hello,
I have a table containing x y z coordinates. But I have no geometry column?
Is it possible to find the k nearest neighbors of any point. Is there
something like a kd-tree Index in postgres???
I know, if i had a geometry column I could make use of the distance
function to find the k nearest neighbors. But my table has millions of
records, thus it would take a very long time to use the distance
function for each point.
Thanks in advance.
Andi

Maybe you can partition your 3d space into cubes and add one colum to the table precalculating the cube
that owns the point.

For an arbitrary point you can calculate the cube that contains it and surrounding boxes and
restrict full distance calculation to records belonging to those cubes.

for millions of points seems to be faster than trying all points blindy (despite of being indexed).
--
->>-----------------------------------------------
Clist UAH a.k.a Angel
---------------------------------[www.uah.es]-<<--
""

[Merlin Moncure]

Post by Andreas Jochem
Hello,
I have a table containing x y z coordinates. But I have no geometry column?
Is it possible to find the k nearest neighbors of any point. Is there
something like a kd-tree Index in postgres???

cubes:
http://www.postgresql.org/docs/8.3/interactive/cube.html

merlin