pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Alexander Staubo <alex@purefiction.net>
To: Andrew Lazarus <andrew@pillette.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: index structure for 114-dimension vector
Date: Fri, 27 Apr 2007 00:34:36 +0200
Message-ID: <88daf38c0704261534n2a6d3ab8g57482bae8672da53@mail.gmail.com> (raw)
In-Reply-To: <1217328326.20070420120729@pillette.com>
References: <b42b73150704170917n33ebcdc8wc852a3fa02fd8bb5@mail.gmail.com>
	<01db01c781e4$c700bf30$2e00a8c0@tridecap.com>
	<b42b73150704181716wb1600aey8761b6793d3fd702@mail.gmail.com>
	<1217328326.20070420120729@pillette.com>

On 4/20/07, Andrew Lazarus <andrew@pillette.com> wrote:
> I have a table with 2.5 million real[] arrays. (They are points in a
> time series.) Given a new array X, I'd like to find, say, the 25
> closest to X in some sense--for simplification, let's just say in the
> usual vector norm. Speed is critical here, and everything I have tried
> has been too slow.

Let me chime in with the observation that this is a multidimensional
nearest neighbour (reverse nearest neighbour and its close cousin,
k-NN) that is well known in statistics, and particularly relevant to
statistical learning and classification. Knowing the jargon might help
you dig up efficient algorithms to mine your data; there are tons of
fascinating papers available through Citeseer.

In particular, I recommend the paper "Efficient k-NN Search on
Vertically Decomposed Data" by de Vries et al, SIGMOD 2002 (PDF here:
http://citeseer.ist.psu.edu/618138.html), if only for inspiration. It
proposes an algorithm called BOND to drastically reduce the search
space by probalistic means. They give an example using image
histograms, but the algorithm applies to any multidimensional data.
Briefly put, it points out that proximity comparison can be computed
vertically, a few dimensions at a time, and entire subsets can be
thrown away when it's apparent that they are below a statistically
derived lower bound. The only gotcha is that the algorithm derives
much of its performance from the assumption that your data is
vertically decomposed, one table per dimension, otherwise the search
effectively incurs a sequential scan of the entire dataset, and then
you're pretty much back to square one.

The most common approach to nearest neighbour search is to use a
spatial data structure. The classic algorithm is the kd-tree
(http://en.wikipedia.org/wiki/Kd-tree) and there's the newer K-D-B
tree, neither of which are available in PostgreSQL. If I remember
correctly, R-trees have also been shown to be useful for high numbers
of dimensions; with PostgreSQL you have R-trees and even better
R-tree-equivalent support through GiST. I have no idea whether you can
actually munge your integer vectors into something GiST can index and
search, but it's a thought. (GiST, presumably, can also theoretically
index kd-trees and other spatial trees.)

Alexander.



view thread (12+ messages)  latest in thread

Message-ID: <88daf38c0704261534n2a6d3ab8g57482bae8672da53@mail.gmail.com>
Permalink:  ../88daf38c0704261534n2a6d3ab8g57482bae8672da53@mail.gmail.com/
Also on:    postgresql.org/message-id/88daf38c0704261534n2a6d3ab8g57482bae8672da53@mail.gmail.com

 · 

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 from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-performance@postgresql.org
  Cc: alex@purefiction.net, andrew@pillette.com
  Subject: Re: index structure for 114-dimension vector
  In-Reply-To: <88daf38c0704261534n2a6d3ab8g57482bae8672da53@mail.gmail.com>
  References: <b42b73150704170917n33ebcdc8wc852a3fa02fd8bb5@mail.gmail.com> <01db01c781e4$c700bf30$2e00a8c0@tridecap.com> <b42b73150704181716wb1600aey8761b6793d3fd702@mail.gmail.com> <1217328326.20070420120729@pillette.com> <88daf38c0704261534n2a6d3ab8g57482bae8672da53@mail.gmail.com>

* 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