pg.ddx.io pgsql-admin@postgresql.org mailing list archive
help / color / mirror / Atom feedFunction which gives back the nearest neighbours of a requested value
6+ messages / 4 participants
[nested] [flat]
* Function which gives back the nearest neighbours of a requested value
@ 2005-03-25 18:36 Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
2005-03-27 05:24 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Christopher Kings-Lynne <chriskl@familyhealth.com.au>
0 siblings, 1 reply; 6+ messages in thread
From: Virgile Beddok @ 2005-03-25 18:36 UTC (permalink / raw)
To: pgsql-novice@postgresql.org; +Cc: pgsql-advocacy@postgresql.org; pgsql-admin
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
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [pgsql-advocacy] Function which gives back the nearest neighbours
2005-03-25 18:36 Function which gives back the nearest neighbours of a requested value Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
@ 2005-03-27 05:24 ` Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2005-03-27 16:36 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
0 siblings, 1 reply; 6+ messages in thread
From: Christopher Kings-Lynne @ 2005-03-27 05:24 UTC (permalink / raw)
To: Virgile Beddok <virgile.beddok@igd.fraunhofer.de>; +Cc: pgsql-novice@postgresql.org; pgsql-advocacy@postgresql.org; pgsql-admin
> 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
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [pgsql-advocacy] Function which gives back the nearest neighbours
2005-03-25 18:36 Function which gives back the nearest neighbours of a requested value Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
2005-03-27 05:24 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Christopher Kings-Lynne <chriskl@familyhealth.com.au>
@ 2005-03-27 16:36 ` Bruno Wolff III <bruno@wolff.to>
2005-03-27 16:32 ` Re: [NOVICE] [pgsql-advocacy] Function which gives back the nearest neighbours Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 6+ messages in thread
From: Bruno Wolff III @ 2005-03-27 16:36 UTC (permalink / raw)
To: Christopher Kings-Lynne <chriskl@familyhealth.com.au>; +Cc: Virgile Beddok <virgile.beddok@igd.fraunhofer.de>; pgsql-novice@postgresql.org; pgsql-advocacy@postgresql.org; pgsql-admin
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.
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [NOVICE] [pgsql-advocacy] Function which gives back the nearest neighbours
2005-03-25 18:36 Function which gives back the nearest neighbours of a requested value Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
2005-03-27 05:24 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2005-03-27 16:36 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
@ 2005-03-27 16:32 ` Tom Lane <tgl@sss.pgh.pa.us>
2005-03-28 16:12 ` Re: [NOVICE] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
0 siblings, 1 reply; 6+ messages in thread
From: Tom Lane @ 2005-03-27 16:32 UTC (permalink / raw)
To: Bruno Wolff III <bruno@wolff.to>; +Cc: Christopher Kings-Lynne <chriskl@familyhealth.com.au>; Virgile Beddok <virgile.beddok@igd.fraunhofer.de>; pgsql-novice@postgresql.org; pgsql-advocacy@postgresql.org; pgsql-admin
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
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [NOVICE] Function which gives back the nearest neighbours
2005-03-25 18:36 Function which gives back the nearest neighbours of a requested value Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
2005-03-27 05:24 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2005-03-27 16:36 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
2005-03-27 16:32 ` Re: [NOVICE] [pgsql-advocacy] Function which gives back the nearest neighbours Tom Lane <tgl@sss.pgh.pa.us>
@ 2005-03-28 16:12 ` Bruno Wolff III <bruno@wolff.to>
2005-03-28 17:22 ` Re: [NOVICE] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
0 siblings, 1 reply; 6+ messages in thread
From: Bruno Wolff III @ 2005-03-28 16:12 UTC (permalink / raw)
To: Virgile Beddok <virgile.beddok@igd.fraunhofer.de>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Christopher Kings-Lynne <chriskl@familyhealth.com.au>; pgsql-novice@postgresql.org; pgsql-advocacy@postgresql.org
On Mon, Mar 28, 2005 at 17:52:21 +0200,
Virgile Beddok <virgile.beddok@igd.fraunhofer.de> wrote:
> Thanks for the help.
> I'll try this for the one-dimensional search.
> For the muti-dimensional one, which tools of postgresql could I use for
> this metric function, or this indexable search, which Bruno mentioned.
> Do they already exist?
> What about using a tree for that? Is there one which could fit to such a
> "nearest neighbour search", or do I have to implement it myself...
You could look at boxes or cubes. You haven't said enough about your
multidimensional problem to give specific answers.
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [NOVICE] Function which gives back the nearest neighbours
2005-03-25 18:36 Function which gives back the nearest neighbours of a requested value Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
2005-03-27 05:24 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2005-03-27 16:36 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
2005-03-27 16:32 ` Re: [NOVICE] [pgsql-advocacy] Function which gives back the nearest neighbours Tom Lane <tgl@sss.pgh.pa.us>
2005-03-28 16:12 ` Re: [NOVICE] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
@ 2005-03-28 17:22 ` Bruno Wolff III <bruno@wolff.to>
0 siblings, 0 replies; 6+ messages in thread
From: Bruno Wolff III @ 2005-03-28 17:22 UTC (permalink / raw)
To: Virgile Beddok <virgile.beddok@igd.fraunhofer.de>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Christopher Kings-Lynne <chriskl@familyhealth.com.au>; pgsql-novice@postgresql.org; pgsql-advocacy@postgresql.org
On Mon, Mar 28, 2005 at 18:32:09 +0200,
Virgile Beddok <virgile.beddok@igd.fraunhofer.de> wrote:
>
> I just want to know if there is an existing and implemented function, or
> tree, in Postgres which allows me to directly perform a "nearest neighbour
> search" on multidimensional vectors.
How are you measuring distance? (i.e. Euclidean distance isn't the only
metric that you could be using.)
Earthdistance has functions for doing this using geodesics on the surface
of a sphere.
For 2D, I think there is a function on "point"s that uses Euclidean
distance.
I don't think this is the hard part of your problem. It is easy to create
a metric function and get the point corresponding to the minimal value
using a sort. Being able to limit the sets of points looked at is the
hard part.
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~2005-03-28 17:22 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2005-03-25 18:36 Function which gives back the nearest neighbours of a requested value Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
2005-03-27 05:24 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2005-03-27 16:36 ` Re: [pgsql-advocacy] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
2005-03-27 16:32 ` Re: [NOVICE] [pgsql-advocacy] Function which gives back the nearest neighbours Tom Lane <tgl@sss.pgh.pa.us>
2005-03-28 16:12 ` Re: [NOVICE] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
2005-03-28 17:22 ` Re: [NOVICE] Function which gives back the nearest neighbours Bruno Wolff III <bruno@wolff.to>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox