pg.ddx.io  pgsql-admin@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Bruno Wolff III <bruno@wolff.to>
Cc: Christopher Kings-Lynne <chriskl@familyhealth.com.au>
Cc: Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
Cc: pgsql-novice@postgresql.org
Cc: pgsql-advocacy@postgresql.org
Subject: Re: [NOVICE] Function which gives back the
Date: Mon, 28 Mar 2005 17:52:21 +0200 (CEST)
Message-ID: <1218.146.140.8.94.1112025141.squirrel@webmail.igd.fraunhofer.de> (raw)
In-Reply-To: <5796.1111941132@sss.pgh.pa.us>
References: <2657.146.140.8.144.1111775776.squirrel@webmail.igd.fraunhofer.de>
	<42464392.9040903@familyhealth.com.au>
	<20050327163653.GH9280@wolff.to>
	<5796.1111941132@sss.pgh.pa.us>

> 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...
>
> 			regards, tom lane

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



view thread (3+ messages)  latest in thread

Message-ID: <1218.146.140.8.94.1112025141.squirrel@webmail.igd.fraunhofer.de>
Permalink:  ../1218.146.140.8.94.1112025141.squirrel@webmail.igd.fraunhofer.de/
Also on:    postgresql.org/message-id/1218.146.140.8.94.1112025141.squirrel@webmail.igd.fraunhofer.de

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-admin@postgresql.org
  Cc: virgile.beddok@igd.fraunhofer.de, tgl@sss.pgh.pa.us, bruno@wolff.to, chriskl@familyhealth.com.au, pgsql-novice@postgresql.org, pgsql-advocacy@postgresql.org
  Subject: Re: [NOVICE] Function which gives back the
  In-Reply-To: <1218.146.140.8.94.1112025141.squirrel@webmail.igd.fraunhofer.de>
  References: <2657.146.140.8.144.1111775776.squirrel@webmail.igd.fraunhofer.de> <42464392.9040903@familyhealth.com.au> <20050327163653.GH9280@wolff.to> <5796.1111941132@sss.pgh.pa.us> <1218.146.140.8.94.1112025141.squirrel@webmail.igd.fraunhofer.de>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

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