X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by postgresql.org (Postfix) with ESMTP id 40E849DCB99 for ; Fri, 20 Jan 2006 18:59:28 -0400 (AST) Received: from postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 97917-10 for ; Fri, 20 Jan 2006 18:59:28 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- Received: from cassarossa.samfundet.no (cassarossa.samfundet.no [129.241.93.19]) by postgresql.org (Postfix) with ESMTP id 0A45F9DCB9D for ; Fri, 20 Jan 2006 18:59:23 -0400 (AST) Received: from trofast.sesse.net ([129.241.93.32]) by cassarossa.samfundet.no with esmtp (Exim 4.50) id 1F05E6-0003ip-BG for pgsql-performance@postgresql.org; Fri, 20 Jan 2006 23:59:26 +0100 Received: from sesse by trofast.sesse.net with local (Exim 3.36 #1 (Debian)) id 1F05EC-00076k-00 for ; Fri, 20 Jan 2006 23:59:32 +0100 Date: Fri, 20 Jan 2006 23:59:32 +0100 From: "Steinar H. Gunderson" To: pgsql-performance@postgresql.org Subject: Re: [GENERAL] Creation of tsearch2 index is very slow Message-ID: <20060120225932.GB27230@uio.no> Mail-Followup-To: pgsql-performance@postgresql.org References: <20060120170452.GC31908@svana.org> <26153.1137784469@sss.pgh.pa.us> <20060120201036.GE31908@svana.org> <26583.1137788505@sss.pgh.pa.us> <20060120205132.GF31908@svana.org> <26958.1137791955@sss.pgh.pa.us> <20060120213754.GG31908@svana.org> <27264.1137793817@sss.pgh.pa.us> <20060120221655.GA22581@uio.no> <7.0.1.0.2.20060120172335.039f5e20@earthlink.net> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <7.0.1.0.2.20060120172335.039f5e20@earthlink.net> X-Operating-System: Linux 2.6.14.3 on a x86_64 X-Message-Flag: Outlook? --> http://www.mozilla.org/products/thunderbird/ User-Agent: Mutt/1.5.11 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.07 required=5 tests=[AWL=0.070] X-Spam-Score: 0.07 X-Spam-Level: X-Archive-Number: 200601/376 X-Sequence-Number: 16854 On Fri, Jan 20, 2006 at 05:29:46PM -0500, Ron wrote: > If the N-dimensional space is Euclidean (any is the same > distance apart in dimension x), then finding the farthest pair can be > done in at least O(n). That sounds a bit optimistic. http://portal.acm.org/ft_gateway.cfm?id=167217&type=pdf&coll=GUIDE&dl=GUIDE&CFID=66230761&CFTOKEN=72453878 is from 1993, but still it struggles with getting it down to O(n log n) deterministically, for Euclidian 3-space, and our problem is not Euclidian (although it still satisfies the triangle inequality, which sounds important to me) and in a significantly higher dimension... /* Steinar */ -- Homepage: http://www.sesse.net/