private BoundedPriorityQueue < Result > computeKnnSDC ( int k , int iid ) { BoundedPriorityQueue < Result > nn = new BoundedPriorityQueue < Result > ( new Result ( ) , k ) ; // find the product quantization code of the vector with the given id, i.e the centroid indices int [ ] pqCodeQuery = new int [ numSubVectors ] ; for ( int m = 0 ; m < numSubVectors ; m ++ ) { if ( pqByteCodes != null ) { pqCodeQuery [ m ] = pqByteCodes . getQuick ( iid * numSubVectors + m ) ; } else { pqCodeQuery [ m ] = pqShortCodes . getQuick ( iid * numSubVectors + m ) ; } } double lowest = Double . MAX_VALUE ; for ( int i = 0 ; i < loadCounter ; i ++ ) { double l2distance = 0 ; for ( int j = 0 ; j < numSubVectors ; j ++ ) { int pqSubCode = pqByteCodes . getQuick ( i * numSubVectors + j ) ; int pqSubCodeQuery = pqCodeQuery [ j ] ; if ( pqByteCodes != null ) { // plus 128 because byte range is -128..127 pqSubCode += 128 ; pqSubCodeQuery += 128 ; } for ( int m = 0 ; m < subVectorLength ; m ++ ) { l2distance += ( productQuantizer [ j ] [ pqSubCode ] [ m ] - productQuantizer [ j ] [ pqSubCodeQuery ] [ m ] ) * ( productQuantizer [ j ] [ pqSubCode ] [ m ] - productQuantizer [ j ] [ pqSubCodeQuery ] [ m ] ) ; if ( l2distance > lowest ) { break ; // break the inner loop } } if ( l2distance > lowest ) { break ; // break the outer loop } } nn . offer ( new Result ( i , l2distance ) ) ; if ( i >= k ) { lowest = nn . last ( ) . getDistance ( ) ; } } return nn ; }
Computes and returns the k nearest neighbors of the query internal id using the SDC approach .