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 86E8B9DCB53 for ; Fri, 20 Jan 2006 18:16:53 -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 91234-06 for ; Fri, 20 Jan 2006 18:16:52 -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 E62129DCAE0 for ; Fri, 20 Jan 2006 18:16:48 -0400 (AST) Received: from trofast.sesse.net ([129.241.93.32]) by cassarossa.samfundet.no with esmtp (Exim 4.50) id 1F04Ys-0003Sz-BM for pgsql-performance@postgresql.org; Fri, 20 Jan 2006 23:16:50 +0100 Received: from sesse by trofast.sesse.net with local (Exim 3.36 #1 (Debian)) id 1F04Yx-0006f9-00 for ; Fri, 20 Jan 2006 23:16:55 +0100 Date: Fri, 20 Jan 2006 23:16:55 +0100 From: "Steinar H. Gunderson" To: pgsql-performance@postgresql.org Subject: Re: [GENERAL] Creation of tsearch2 index is very slow Message-ID: <20060120221655.GA22581@uio.no> Mail-Followup-To: pgsql-performance@postgresql.org References: <43D0ED57.1020608@gmx.de> <17454.1137771321@sss.pgh.pa.us> <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> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <27264.1137793817@sss.pgh.pa.us> 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.072 required=5 tests=[AWL=0.072] X-Spam-Score: 0.072 X-Spam-Level: X-Archive-Number: 200601/369 X-Sequence-Number: 16847 On Fri, Jan 20, 2006 at 04:50:17PM -0500, Tom Lane wrote: > I wonder if there is a way to improve on that. Ooh, the farthest pair problem (in an N-dimensional vector space, though). I'm pretty sure problems like this has been studied quite extensively in the literature, although perhaps not with the same norm. It's known under both "farthest pair" and "diameter", and probably others. I'm fairly sure it should be solvable in at least O(n log n). /* Steinar */ -- Homepage: http://www.sesse.net/