pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Steinar H. Gunderson <sgunderson@bigfoot.com>
To: pgsql-performance@postgresql.org
Subject: Re: [GENERAL] Creation of tsearch2 index is very slow
Date: Sat, 21 Jan 2006 00:28:43 +0100
Message-ID: <20060120232842.GA28433@uio.no> (raw)
In-Reply-To: <27264.1137793817@sss.pgh.pa.us>
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>

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/



view thread (38+ messages)  latest in thread

Message-ID: <20060120232842.GA28433@uio.no>
Permalink:  ../20060120232842.GA28433@uio.no/
Also on:    postgresql.org/message-id/20060120232842.GA28433@uio.no

 · 

reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-performance@postgresql.org
  Cc: sgunderson@bigfoot.com
  Subject: Re: [GENERAL] Creation of tsearch2 index is very slow
  In-Reply-To: <20060120232842.GA28433@uio.no>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox