private BoundedPriorityQueue < Result > computeKnnIVFADC ( int k , double [ ] qVector ) throws Exception { BoundedPriorityQueue < Result > nn = new BoundedPriorityQueue < Result > ( new Result ( ) , k ) ; // find the w nearest coarse centroids int [ ] nearestCoarseCentroidIndices = computeNearestCoarseIndices ( qVector , w ) ; for ( int i = 0 ; i < w ; i ++ ) { // for each assignment // quantize to the i-th closest centroid of the coarse quantizer and compute residual vector int nearestCoarseIndex = nearestCoarseCentroidIndices [ i ] ; double [ ] residualVectorQuery = computeResidualVector ( qVector , nearestCoarseIndex ) ; // apply a random transformation if needed if ( transformation == TransformationType . RandomRotation ) { residualVectorQuery = rr . rotate ( residualVectorQuery ) ; } else if ( transformation == TransformationType . RandomPermutation ) { residualVectorQuery = rp . permute ( residualVectorQuery ) ; } // compute lookup table double [ ] [ ] lookUpTable = computeLookupADC ( residualVectorQuery ) ; for ( int j = 0 ; j < invertedLists [ nearestCoarseIndex ] . size ( ) ; j ++ ) { int iid = invertedLists [ nearestCoarseIndex ] . getQuick ( j ) ; double l2distance = 0 ; int codeStart = j * numSubVectors ; if ( numProductCentroids <= 256 ) { byte [ ] pqCode = pqByteCodes [ nearestCoarseIndex ] . toArray ( codeStart , numSubVectors ) ; for ( int m = 0 ; m < pqCode . length ; m ++ ) { // plus 128 because byte range is -128..127 l2distance += lookUpTable [ m ] [ pqCode [ m ] + 128 ] ; } } else { short [ ] pqCode = pqShortCodes [ nearestCoarseIndex ] . toArray ( codeStart , numSubVectors ) ; for ( int m = 0 ; m < pqCode . length ; m ++ ) { l2distance += lookUpTable [ m ] [ pqCode [ m ] ] ; } } nn . offer ( new Result ( iid , l2distance ) ) ; } } return nn ; }
Computes and returns the k nearest neighbors of the query vector using the IVFADC approach .