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 4DAC29DC83F for ; Fri, 20 Jan 2006 19:28:39 -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 05198-05 for ; Fri, 20 Jan 2006 19:28:40 -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 5D70B9DCB93 for ; Fri, 20 Jan 2006 19:28:35 -0400 (AST) Received: from trofast.ipv6.sesse.net ([2001:700:300:dc03:20e:cff:fe36:a766] helo=trofast.sesse.net) by cassarossa.samfundet.no with esmtp (Exim 4.50) id 1F05gK-0003sT-TQ for pgsql-performance@postgresql.org; Sat, 21 Jan 2006 00:28:37 +0100 Received: from sesse by trofast.sesse.net with local (Exim 3.36 #1 (Debian)) id 1F05gR-0007Ph-00 for ; Sat, 21 Jan 2006 00:28:43 +0100 Date: Sat, 21 Jan 2006 00:28:43 +0100 From: "Steinar H. Gunderson" To: pgsql-performance@postgresql.org Subject: Re: [GENERAL] Creation of tsearch2 index is very slow Message-ID: <20060120232842.GA28433@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.069 required=5 tests=[AWL=0.069] X-Spam-Score: 0.069 X-Spam-Level: X-Archive-Number: 200601/378 X-Sequence-Number: 16856 On Fri, Jan 20, 2006 at 04:50:17PM -0500, Tom Lane wrote: > I wonder if there is a way to improve on that. http://www.cs.uwaterloo.ca/~tmchan/slide_isaac.ps: The diameter problem has been studied extensively in the traditional model. Although O(n log n) algorithms have been given for d = 2 and d = 3, only slightly subquadratic algorithms are known for higher dimensions. It doesn't mention a date, but has references to at least 2004-papers, so I'm fairly sure nothing big has happened since that. It sounds like we either want to go for an approximation, or just accept that it's a lot of work to get it better than O(n^2). Or, of course, find some special property of our problem that makes it easier than the general problem :-) /* Steinar */ -- Homepage: http://www.sesse.net/