Thread: Function which gives back the nearest neighbours of a requested value

Hi!

I'm looking for an existing function which allows me to search the nearest
neighbours of the requested value.

A simple example: if I search the value "2", and my table doesn't contain
it, but only contains "0" and "10", as "nearest neighbours", then it will
give me back these values : "0" and "10".
Could you please tell me if such function already exists in Postgresql,
for  one-dimensional objects, and also for multi-dimensional objects.

Thanks a lot in advance.
Virgile Beddok

> I'm looking for an existing function which allows me to search the nearest
> neighbours of the requested value.

Well you could try something like:

SELECT * FROM table ORDER BY ABS(val - 2) LIMIT 1;

That doesn't get you all the way there, but it's an idea...

Chris

On Sun, Mar 27, 2005 at 13:24:34 +0800,
  Christopher Kings-Lynne <chriskl@familyhealth.com.au> wrote:
> >I'm looking for an existing function which allows me to search the nearest
> >neighbours of the requested value.
>
> Well you could try something like:
>
> SELECT * FROM table ORDER BY ABS(val - 2) LIMIT 1;
>
> That doesn't get you all the way there, but it's an idea...

For multidimensional objects you can do the same thing with a distance
metric function. It will be relatively slow since this won't be indexable
and will require a sort of all of the values. If you have some bound on
how far apart points can be, then you might be able to limit the set
of candidate points using an indexable search.

Bruno Wolff III <bruno@wolff.to> writes:
> On Sun, Mar 27, 2005 at 13:24:34 +0800,
>   Christopher Kings-Lynne <chriskl@familyhealth.com.au> wrote:
>>> I'm looking for an existing function which allows me to search the nearest
>>> neighbours of the requested value.
>>
>> Well you could try something like:
>>
>> SELECT * FROM table ORDER BY ABS(val - 2) LIMIT 1;
>>
>> That doesn't get you all the way there, but it's an idea...

> For multidimensional objects you can do the same thing with a distance
> metric function. It will be relatively slow since this won't be indexable
> and will require a sort of all of the values. If you have some bound on
> how far apart points can be, then you might be able to limit the set
> of candidate points using an indexable search.

I'd probably go with looking for the nearest "above" neighbor and
nearest "below" neighbor separately, eg

    select * from tab where val > 'target' order by val limit 1;
    select * from tab where val < 'target' order by val desc limit 1;

If there's an index on val, this should work really well.  Of course, if
"nearest" is being defined in multidimensional terms as Bruno is
imagining, it doesn't work at all...

BTW, why is this thread cross-posted to so many lists?  It seems
off-topic for at least two of 'em.

            regards, tom lane