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: Fri, 20 Jan 2006 23:59:32 +0100
Message-ID: <20060120225932.GB27230@uio.no> (raw)
In-Reply-To: <7.0.1.0.2.20060120172335.039f5e20@earthlink.net>
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>

On Fri, Jan 20, 2006 at 05:29:46PM -0500, Ron wrote:
> If the N-dimensional space is Euclidean (any <x, x+1> 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=662...

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/



view thread (38+ messages)  latest in thread

Message-ID: <20060120225932.GB27230@uio.no>
Permalink:  ../20060120225932.GB27230@uio.no/
Also on:    postgresql.org/message-id/20060120225932.GB27230@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: <20060120225932.GB27230@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