private double kdKNNSearch(int left,int right,int axis,O query,KNNHeap knns,DBIDArrayIter iter,double maxdist){
  if (right - left <= leafsize) {
    for (iter.seek(left); iter.getOffset() < right; iter.advance()) {
      double dist=norm.distance(query,relation.get(iter));
      countObjectAccess();
      countDistanceComputation();
      if (dist <= maxdist) {
        knns.insert(dist,iter);
      }
      maxdist=knns.getKNNDistance();
    }
    return maxdist;
  }
  final int middle=(left + right) >>> 1;
  O split=relation.get(iter.seek(middle));
  countObjectAccess();
  final double delta=split.doubleValue(axis) - query.doubleValue(axis);
  final boolean onleft=(delta >= 0);
  final boolean onright=(delta <= 0);
  final int next=(axis + 1) % dims;
  if (onleft && onright) {
    double dist=norm.distance(query,split);
    countDistanceComputation();
    if (dist <= maxdist) {
      assert (iter.getOffset() == middle);
      knns.insert(dist,iter);
      maxdist=knns.getKNNDistance();
    }
    if (left < middle) {
      maxdist=kdKNNSearch(left,middle,next,query,knns,iter,maxdist);
    }
    if (middle + 1 < right) {
      maxdist=kdKNNSearch(middle + 1,right,next,query,knns,iter,maxdist);
    }
  }
 else {
    if (onleft) {
      if (left < middle) {
        maxdist=kdKNNSearch(left,middle,next,query,knns,iter,maxdist);
      }
      if (Math.abs(delta) <= maxdist) {
        double dist=norm.distance(query,split);
        countDistanceComputation();
        if (dist <= maxdist) {
          knns.insert(dist,iter.seek(middle));
          maxdist=knns.getKNNDistance();
        }
      }
      if ((middle + 1 < right) && (Math.abs(delta) <= maxdist)) {
        maxdist=kdKNNSearch(middle + 1,right,next,query,knns,iter,maxdist);
      }
    }
 else {
      if (middle + 1 < right) {
        maxdist=kdKNNSearch(middle + 1,right,next,query,knns,iter,maxdist);
      }
      if (Math.abs(delta) <= maxdist) {
        double dist=norm.distance(query,split);
        countDistanceComputation();
        if (dist <= maxdist) {
          knns.insert(dist,iter.seek(middle));
          maxdist=knns.getKNNDistance();
        }
      }
      if ((left < middle) && (Math.abs(delta) <= maxdist)) {
        maxdist=kdKNNSearch(left,middle,next,query,knns,iter,maxdist);
      }
    }
  }
  return maxdist;
}

private double kdKNNSearch ( int left , int right , int axis , O query , KNNHeap knns , DBIDArrayIter iter , double maxdist ) { if ( right - left <= leafsize ) { for ( iter . seek ( left ) ; iter . getOffset ( ) < right ; iter . advance ( ) ) { double dist = norm . distance ( query , relation . get ( iter ) ) ; countObjectAccess ( ) ; countDistanceComputation ( ) ; if ( dist <= maxdist ) { knns . insert ( dist , iter ) ; } maxdist = knns . getKNNDistance ( ) ; } return maxdist ; } final int middle = ( left + right ) > > > 1 ; O split = relation . get ( iter . seek ( middle ) ) ; countObjectAccess ( ) ; final double delta = split . doubleValue ( axis ) - query . doubleValue ( axis ) ; final boolean onleft = ( delta >= 0 ) ; final boolean onright = ( delta <= 0 ) ; final int next = ( axis + 1 ) % dims ; if ( onleft && onright ) { double dist = norm . distance ( query , split ) ; countDistanceComputation ( ) ; if ( dist <= maxdist ) { assert ( iter . getOffset ( ) == middle ) ; knns . insert ( dist , iter ) ; maxdist = knns . getKNNDistance ( ) ; } if ( left < middle ) { maxdist = kdKNNSearch ( left , middle , next , query , knns , iter , maxdist ) ; } if ( middle + 1 < right ) { maxdist = kdKNNSearch ( middle + 1 , right , next , query , knns , iter , maxdist ) ; } } else { if ( onleft ) { if ( left < middle ) { maxdist = kdKNNSearch ( left , middle , next , query , knns , iter , maxdist ) ; } if ( Math . abs ( delta ) <= maxdist ) { double dist = norm . distance ( query , split ) ; countDistanceComputation ( ) ; if ( dist <= maxdist ) { knns . insert ( dist , iter . seek ( middle ) ) ; maxdist = knns . getKNNDistance ( ) ; } } if ( ( middle + 1 < right ) && ( Math . abs ( delta ) <= maxdist ) ) { maxdist = kdKNNSearch ( middle + 1 , right , next , query , knns , iter , maxdist ) ; } } else { if ( middle + 1 < right ) { maxdist = kdKNNSearch ( middle + 1 , right , next , query , knns , iter , maxdist ) ; } if ( Math . abs ( delta ) <= maxdist ) { double dist = norm . distance ( query , split ) ; countDistanceComputation ( ) ; if ( dist <= maxdist ) { knns . insert ( dist , iter . seek ( middle ) ) ; maxdist = knns . getKNNDistance ( ) ; } } if ( ( left < middle ) && ( Math . abs ( delta ) <= maxdist ) ) { maxdist = kdKNNSearch ( left , middle , next , query , knns , iter , maxdist ) ; } } } return maxdist ; }
perform a knn search on the kd - tree .
