Обсуждение: 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
Re: [pgsql-advocacy] Function which gives back the nearest neighbours
От
Christopher Kings-Lynne
Дата:
> 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