Re: Nearest neighbour search with arbitrary distance function

On 1 Jun 2000, Philip Lijnzaad wrote:

> On 1 Jun 2000 16:41:40 GMT,
> "Sam" == Sameer Siruguri <siruguri_at_cs.rice.edu> writes:
>
> Sam> I would like to do an efficient nearest neighour search on
> Sam> multidimensional vector spaces with arbitrary distance
> Sam> functions. Kd-trees are a viable alternative but they only work for
> Sam> "coordinate" based metrics. In particular, how would I do an efficient
> Sam> nearest neighbour search with the cosine distance function?
>
> This is probably not the right newsgroup for this; it's predominantly
> relational stuff here. Better to try sci.math or simply www.deja.com.
> Anyways, a quick search on www.google.com using 'Kd-trees searching vector
> space' showed _lots_ of hits; if this is not enough, try Knuth or Preparata,
> "Computational Geometry". www.amazon.com will point out similar books. Cheers,
>
> Philip

I disagree, I think this does belong in this newsgroup. Multdimensional indices are a hot topic (well...) in db research (even relational). For the original poster: you can check the Hybrid Tree which is a disk based adapation of the kd tree and rtree (ie. combining space and data partitioning methods) and supports arbitrary distance metrics. You can check it out at http://www-db.ics.uci.edu. Look in the publications. Michael

>
> --
> /dev/brain: character special (53/0)
> -----------------------------------------------------------------------------
> Philip Lijnzaad, lijnzaad_at_ebi.ac.uk \ European Bioinformatics Institute,rm A2-24
> +44 (0)1223 49 4639 / Wellcome Trust Genome Campus, Hinxton
> +44 (0)1223 49 4468 (fax) \ Cambridgeshire CB10 1SD, GREAT BRITAIN
> PGP fingerprint: E1 03 BF 80 94 61 B6 FC 50 3D 1F 64 40 75 FB 53
>

---
Michael Ortega-Binderberger        miki_at_acm.org, miki_at_ics.uci.edu
                                   miki_at_computer.org, m.ortega_at_ieee.org
Department of Computer Science     http://www-db.ics.uci.edu/~miki
U. of Illinois, Urbana Champaign   949-824-7231 fax: 949-824-4056 
                                   444 Computer Science, 
On loan to the University of       U of California at Irvine,
California, Irvine (Researcher)    Irvine, CA, 92697-3425