private void fastABOD ( Database db , Relation < V > relation , DBIDs ids , WritableDoubleDataStore abodvalues , DoubleMinMax minmaxabod ) { // Build a kernel matrix, to make O(n^3) slightly less bad. SimilarityQuery < V > sq = db . getSimilarityQuery ( relation , kernelFunction ) ; KernelMatrix kernelMatrix = new KernelMatrix ( sq , relation , ids ) ; MeanVariance s = new MeanVariance ( ) ; KNNHeap nn = DBIDUtil . newHeap ( k ) ; for ( DBIDIter pA = ids . iter ( ) ; pA . valid ( ) ; pA . advance ( ) ) { final double simAA = kernelMatrix . getSimilarity ( pA , pA ) ; // Choose the k-min nearest nn . clear ( ) ; for ( DBIDIter nB = relation . iterDBIDs ( ) ; nB . valid ( ) ; nB . advance ( ) ) { if ( DBIDUtil . equal ( nB , pA ) ) { continue ; } double simBB = kernelMatrix . getSimilarity ( nB , nB ) ; double simAB = kernelMatrix . getSimilarity ( pA , nB ) ; double sqdAB = simAA + simBB - simAB - simAB ; if ( ! ( sqdAB > 0. ) ) { continue ; } nn . insert ( sqdAB , nB ) ; } KNNList nl = nn . toKNNList ( ) ; s . reset ( ) ; DoubleDBIDListIter iB = nl . iter ( ) , iC = nl . iter ( ) ; for ( ; iB . valid ( ) ; iB . advance ( ) ) { double sqdAB = iB . doubleValue ( ) ; double simAB = kernelMatrix . getSimilarity ( pA , iB ) ; if ( ! ( sqdAB > 0. ) ) { continue ; } for ( iC . seek ( iB . getOffset ( ) + 1 ) ; iC . valid ( ) ; iC . advance ( ) ) { double sqdAC = iC . doubleValue ( ) ; double simAC = kernelMatrix . getSimilarity ( pA , iC ) ; if ( ! ( sqdAC > 0. ) ) { continue ; } // Exploit bilinearity of scalar product: // <B-A, C-A> = <B, C-A> - <A,C-A> // = <B,C> - <B,A> - <A,C> + <A,A> double simBC = kernelMatrix . getSimilarity ( iB , iC ) ; double numerator = simBC - simAB - simAC + simAA ; double div = 1. / ( sqdAB * sqdAC ) ; s . put ( numerator * div , FastMath . sqrt ( div ) ) ; } } final double abof = s . getNaiveVariance ( ) ; minmaxabod . put ( abof ) ; abodvalues . putDouble ( pA , abof ) ; } }
Full kernel - based version .