From: Arjen van der Meijden <acmmailing@tweakers.net>
To: Mark Kirkwood <markir@paradise.net.nz>
Cc: Jeff Davis <pgsql@j-davis.com>
Cc: Andrew Lazarus <andrew@pillette.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: index structure for 114-dimension vector
Date: Fri, 27 Apr 2007 08:07:38 +0200
Message-ID: <4631932A.6000000@tweakers.net> (raw)
In-Reply-To: <46294FEB.9010909@paradise.net.nz>
References: <b42b73150704170917n33ebcdc8wc852a3fa02fd8bb5@mail.gmail.com>
<01db01c781e4$c700bf30$2e00a8c0@tridecap.com>
<b42b73150704181716wb1600aey8761b6793d3fd702@mail.gmail.com>
<1217328326.20070420120729@pillette.com>
<1177105284.28383.31.camel@dogma.v10.wvs>
<46294FEB.9010909@paradise.net.nz>
On 21-4-2007 1:42 Mark Kirkwood wrote:
> I don't think that will work for the vector norm i.e:
>
> |x - y| = sqrt(sum over j ((x[j] - y[j])^2))
I don't know if this is usefull here, but I was able to rewrite that
algorithm for a set of very sparse vectors (i.e. they had very little
overlapping factors) to something like:
|x - y| = sum over j (x[j]^2) + sum over j (y[j]^2)
+ for each j where x[j] and y[j] are both non-zero: - (x[j]^2 +
y[j]^2) + (x[j] - y[j])^2
The first two parts sums can be calculated only once. So if you have
very little overlap, this is therefore much more efficient (if there is
no overlap at all you end up with x[j]^2 + y[j]^2 anyway). Besides, this
rewritten calculation allows you to store the X and Y vectors using a
trivial table-layout vector(x,i,value) which is only filled with
non-zero's and which you can trivially self-join to find the closest
matches. You don't care about the j's where there is either no x or
y-value anyway with this rewrite.
I can compare over 1000 y's of on average 100 elements to two x's of
over 1000 elements on just a single 1.8Ghz amd processor. (I use it for
a bi-kmeans algorithm, so there are only two buckets to compare to).
So it might be possible to rewrite your algorithm to be less
calculation-intensive. Obviously, with a dense-matrix this isn't going
to work, but there may be other ways to circumvent parts of the
algorithm or to cache large parts of it.
It might also help to extract only the 6 relevant columns into a
seperate temporary table which will have much smaller records and thus
can fit more records per page.
Best regards,
Arjen
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: acmmailing@tweakers.net, markir@paradise.net.nz, pgsql@j-davis.com, andrew@pillette.com
Subject: Re: index structure for 114-dimension vector
In-Reply-To: <4631932A.6000000@tweakers.net>
* 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