5

I have a bunch (~20,000) of large (~200 dimensions) vectors in an unsorted list. I can create a new vector of the same size, and I'd like to find the top N (usually 10 or so) closest (defined by cosine similarity) existing vectors from my list. Right now my approach is to generate a list of vector differences and then sort that and take the top 10, but that takes quite a while (2 or 3 seconds) per comparison, which is fine one at a time but really accumulates when I need to do a bunch at once.

I'm also open to pre-processing of my vector list (I only say it's unsorted since I don't know if it's possible to sort a list of n-dimensional vectors) if that would help. They'll always be the same size of vector. For context, the vectors are results of word2vec.

  • This is tricky, because the cosine similarity is defined by the relationship between two vectors, meaning in order to "make a single pass" for comparison, you'd need to analyze all vectors with all other vectors at least once implying a nested loop or O(n^2) time. You could optimize by saving all calculations but that's 20,000^2 or 400 million. I suppose you could break it down into multiple files. Once you have that, you need only make 10 passes to get the top 10. I'll think on it. – Neil Mar 26 '18 at 7:03
  • Actually, scratch that. (x, y) = (y, x) in this case, so you'd end up with 199,990,000. That's still monstrous, but you could probably grab the top 10 for each chunk handled by a thread and then sort the result. If each chunk was a million, then you'd wind up with a list of 2000 to sort. – Neil Mar 26 '18 at 7:39
  • If you could find a comparison algorithm that produces the same result, but faster, using less elements in the vector for example, that is one way to do it. The other way is to divide up the list into one chunk per CPU, and sort each one on a separate thread, then sort the results (top N from each chunk). – Frank Hileman Mar 26 '18 at 18:20
  • 1
  • As mentioned in the link posted by Frank, random projection is part of the solution; but reducing precision (quantizing each dimension to 1 bit, or plus/minus) is the most important speed-up. Random projection might not work well for word2vec, because randomly lumping together dimensions generated by word2vec seems like it will lead to logically invalid results. Instead, you may need to carefully research how to select (filter away) and combine word2vec dimensions. Remember that the quantizing to 1 bit is the key to speed. – rwong Mar 27 '18 at 0:01
2

I had the same problem -- finding the n smallest of N integers. Note that finding the one smallest requires N comparisons, so my solution uses n*N comparisons to find the n smallest, rather than N^2 for a simple bubble sort. Here's the C code, along with a simple test driver I wrote for this post...

/* --- standard headers --- */
#include <stdio.h>
#include <stdlib.h>

/*===========================================================================
 * Function: nsmallest ( n, nx, x )
 * Purpose:  finds the n smallest values in x[nx], returning their indexes
 * --------------------------------------------------------------------------
 * Arguments: n (I) int containing number of smallest x[nx]'s
 *                  whose indexes are to be returned
 *           nx (I) int containing number of values in x[nx]
 *           x (I)  int* containing nx values, the indexes
 *                  of whose smallest n values are to be returned
 * Returns: (int *) list of indexes containing the smallest
 *                  n values in x[nx].
 * --------------------------------------------------------------------------
 * Notes:     o
 *=========================================================================*/
int *nsmallest ( int n, int nx, int *x ) {
  static int indexes[999];  /* returned indexes of n smallest x[nx]'s */
  int   ix = 0,         /* x[] index */
    index=0, jndex=0,   /* indexes[] indexes */
    nindexes = 1;       /* number of smallest x[]'s found so far */
  indexes[0] = 0;       /* init indexes[] list with first x[] */
  for ( ix=1; ix<nx; ix++ ) {   /* search for n smallest x[nx]'s */
    for ( index=0; index<nindexes; index++ ) { /* compare x[ix] to indexes[] */
      if ( x[ix] < x[indexes[index]] ) { /* put ix before indexes[index] */
        for ( jndex=nindexes-1; jndex>=index; jndex-- ) /* work backwards */
          indexes[jndex+1] = indexes[jndex]; /* move each indexes[] "down" */
        indexes[index] = ix;    /* put current ix in now-vacant slot */
        break;          /* no need for further comparisons */
        } /* --- end-of-if(x[ix]<x[indexes[index]]) --- */
      } /* --- end-of-for(index) --- */
    if ( nindexes < n ) {   /* still need more smallest x[nx]'s */
      if ( index >= nindexes ) indexes[nindexes] = ix; /* ix in last slot */
      nindexes++; }     /* count another smallest x[nx] */
    } /* --- end-of-for(ix) --- */
  return ( indexes );       /* indexes of n smallest x[nx]'s to caller */
  } /* --- end-of-function nsmallest() --- */

#ifdef TESTDRIVE
int main ( int argc, char *argv[] ) {
  int   n     = ( argc>1? atoi(argv[1]) : 10 ),
    nx    = ( argc>2? atoi(argv[2]) : 9999 ),
    seed  = ( argc>3? atoi(argv[3]) : 987654321 );
  double xmax = ( argc>4? (double)atoi(argv[4]) : 999999.0 );
  int   x[99999], ix=0, *indexes=NULL;
  srand(seed);
  for ( ix=0; ix<nx; ix++ )
    x[ix] = (int)( xmax*((double)rand())/((double)RAND_MAX) );
  indexes = nsmallest(n,nx,x);
  printf("%d smallest x[%d]'s...\n",n,nx);
  for ( ix=0; ix<n; ix++ )
    printf("  %d) x[%d] = %d\n", ix+1,indexes[ix],x[indexes[ix]]);
  exit ( 0 );
  } /* --- end-of-main() nsmallest test driver --- */
#endif
/* ------------------------ end-of-file nsmallest.c ---------------------- */

Edit I'd quickly written the above a long time ago for my own purposes, which weren't particularly time-critical, so the posted code was fine for me. But after posting it and looking at it again, I noticed that "index" loop moves forward from smallest to largest, and that means it must go through the entire loop for every candidate number before it can discard that number.

So, mostly just for kicks, I rewrote it going from largest to smallest. Then a candidate can be discarded immediately if it's already larger than the largest small number in the list. And I also (though this was only a very slight improvement) replaced the "jndex" loop, that "makes room" for a newly-found small number, by a single memmove().

And now, testing for the top 150 numbers out of 999000 (I upped the x[] array size for this test), time went down from 0.337secs to 0.012secs. Basically, all numbers are discarded immediately, since it's rare to come across a candidate number smaller than the already-smallest ones. So you're just doing a little bit more than N comparisons, much less than even the earlier n*N, to find the n smallest numbers.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.