pg.ddx.io  pgsql-admin@postgresql.org mailing list archive  
help / color / mirror / Atom feed
Re: [NOVICE] Function which gives back the
3+ messages / 2 participants
[nested] [flat]

* Re: [NOVICE] Function which gives back the
@ 2005-03-28 15:52  Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
  0 siblings, 1 reply; 3+ messages in thread

From: Virgile Beddok @ 2005-03-28 15:52 UTC (permalink / raw)
  To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Bruno Wolff III <bruno@wolff.to>; Christopher Kings-Lynne <chriskl@familyhealth.com.au>; Virgile Beddok <virgile.beddok@igd.fraunhofer.de>; pgsql-novice@postgresql.org; pgsql-advocacy@postgresql.org

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



^ permalink  raw  reply  [nested|flat] 3+ messages in thread

* Re: [NOVICE] Function which gives back the
@ 2005-03-28 16:32  Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
  parent: Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
  0 siblings, 1 reply; 3+ messages in thread

From: Virgile Beddok @ 2005-03-28 16:32 UTC (permalink / raw)
  To: Bruno Wolff III <bruno@wolff.to>; +Cc: Virgile Beddok <virgile.beddok@igd.fraunhofer.de>; 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.
>

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.



^ permalink  raw  reply  [nested|flat] 3+ messages in thread

* Re: [NOVICE] Function which gives back the
@ 2005-04-03 12:14  Bruno Wolff III <bruno@wolff.to>
  parent: Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
  0 siblings, 0 replies; 3+ messages in thread

From: Bruno Wolff III @ 2005-04-03 12:14 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.

What precisely do you mean by "nearest"? To answer that question you
need a metric function. A common metric function is euclidean distance.
Another common one is distance along the geodesic connecting two points
on the surface of the sphere.

The cube contrib package has indexing that might be useful for doing lossy
matches if you have some upperbound on how far a part a nearest neighbor
can be in your problem. It even will handle multiple dimensions. (You
haven't even bothered to tell us how many dimensions your points have.)

The earthdistance contrib package has a function for calculating distance
on the surface of sphere and uses the cube package to provide a lossy
way of doing indexed searches.

If you want specific anwsers it would help if you would provide us with
more details about the problem you are trying to solve.



^ permalink  raw  reply  [nested|flat] 3+ messages in thread


end of thread, other threads:[~2005-04-03 12:14 UTC | newest]

Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2005-03-28 15:52 Re: [NOVICE] Function which gives back the Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
2005-03-28 16:32 ` Virgile Beddok <virgile.beddok@igd.fraunhofer.de>
2005-04-03 12:14   ` 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