X-Original-To: pgsql-admin-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id CCD7053699 for ; Sun, 27 Mar 2005 17:32:37 +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 55626-04 for ; Sun, 27 Mar 2005 16:32:31 +0000 (GMT) Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by svr1.postgresql.org (Postfix) with ESMTP id 918B153683 for ; Sun, 27 Mar 2005 17:32:31 +0100 (BST) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.13.1/8.13.1) with ESMTP id j2RGWCls005797; Sun, 27 Mar 2005 11:32:12 -0500 (EST) To: Bruno Wolff III Cc: Christopher Kings-Lynne , Virgile Beddok , pgsql-novice@postgresql.org, pgsql-advocacy@postgresql.org, pgsql-admin@postgresql.org Subject: Re: [NOVICE] [pgsql-advocacy] Function which gives back the nearest neighbours In-reply-to: <20050327163653.GH9280@wolff.to> References: <2657.146.140.8.144.1111775776.squirrel@webmail.igd.fraunhofer.de> <42464392.9040903@familyhealth.com.au> <20050327163653.GH9280@wolff.to> Comments: In-reply-to Bruno Wolff III message dated "Sun, 27 Mar 2005 10:36:53 -0600" Date: Sun, 27 Mar 2005 11:32:12 -0500 Message-ID: <5796.1111941132@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.006 tagged_above=0 required=5 tests=AWL X-Spam-Level: X-Archive-Number: 200503/449 X-Sequence-Number: 16947 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... BTW, why is this thread cross-posted to so many lists? It seems off-topic for at least two of 'em. regards, tom lane