X-Original-To: pgsql-advocacy-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id 4F60C5336A; Mon, 28 Mar 2005 16:52:29 +0100 (BST) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 85253-09; Mon, 28 Mar 2005 15:52:27 +0000 (GMT) Received: from mailgate2.igd.fraunhofer.de (mailgate2.igd.fraunhofer.de [192.44.32.14]) by svr1.postgresql.org (Postfix) with ESMTP id 1C82E5331B; Mon, 28 Mar 2005 16:52:24 +0100 (BST) Received: from localhost (localhost [127.0.0.1]) by mailgate2.igd.fraunhofer.de (Postfix) with ESMTP id 104BBA96A; Mon, 28 Mar 2005 17:52:25 +0200 (CEST) Received: from webmail.igd.fhg.de (loki.igd.fhg.de [192.44.32.17]) by mailgate2.igd.fraunhofer.de (Postfix) with SMTP id E0D1FFAF; Mon, 28 Mar 2005 17:52:20 +0200 (CEST) Received: from 146.140.8.94 (SquirrelMail authenticated user vbeddok) by webmail.igd.fraunhofer.de with HTTP; Mon, 28 Mar 2005 17:52:21 +0200 (CEST) Message-ID: <1218.146.140.8.94.1112025141.squirrel@webmail.igd.fraunhofer.de> 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> Date: Mon, 28 Mar 2005 17:52:21 +0200 (CEST) Subject: Re: [NOVICE] Function which gives back the From: "Virgile Beddok" To: "Tom Lane" Cc: "Bruno Wolff III" , "Christopher Kings-Lynne" , "Virgile Beddok" , pgsql-novice@postgresql.org, pgsql-advocacy@postgresql.org User-Agent: SquirrelMail/1.4.2 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 Importance: Normal X-Virus-Scanned: by amavisd-new at mailgate2.igd.fraunhofer.de X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0 tagged_above=0 required=5 tests= X-Spam-Level: X-Archive-Number: 200504/16 X-Sequence-Number: 6581 > Bruno Wolff III writes: >> On Sun, Mar 27, 2005 at 13:24:34 +0800, >> Christopher Kings-Lynne 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...