private void preInsert(MkMaxEntry q,MkMaxEntry nodeEntry,KNNHeap knns_q){
  if (LOG.isDebugging()) {
    LOG.debugFine("preInsert " + q + " - "+ nodeEntry+ "\n");
  }
  double knnDist_q=knns_q.getKNNDistance();
  MkMaxTreeNode<O> node=getNode(nodeEntry);
  double knnDist_node=0.;
  if (node.isLeaf()) {
    for (int i=0; i < node.getNumEntries(); i++) {
      MkMaxEntry p=node.getEntry(i);
      double dist_pq=distance(p.getRoutingObjectID(),q.getRoutingObjectID());
      if (dist_pq <= knnDist_q) {
        knns_q.insert(dist_pq,p.getRoutingObjectID());
        if (knns_q.size() >= getKmax()) {
          knnDist_q=knns_q.getKNNDistance();
          q.setKnnDistance(knnDist_q);
        }
      }
      if (dist_pq <= p.getKnnDistance()) {
        KNNList knns_p=knnq.getKNNForDBID(p.getRoutingObjectID(),getKmax() - 1);
        if (knns_p.size() + 1 < getKmax()) {
          p.setKnnDistance(Double.NaN);
        }
 else {
          double knnDist_p=Math.max(dist_pq,knns_p.getKNNDistance());
          p.setKnnDistance(knnDist_p);
        }
      }
      knnDist_node=Math.max(knnDist_node,p.getKnnDistance());
    }
  }
 else {
    List<DoubleIntPair> entries=getSortedEntries(node,q.getRoutingObjectID());
    for (    DoubleIntPair distEntry : entries) {
      MkMaxEntry dirEntry=node.getEntry(distEntry.second);
      double entry_knnDist=dirEntry.getKnnDistance();
      if (distEntry.second < entry_knnDist || distEntry.second < knnDist_q) {
        preInsert(q,dirEntry,knns_q);
        knnDist_q=knns_q.getKNNDistance();
      }
      knnDist_node=Math.max(knnDist_node,dirEntry.getKnnDistance());
    }
  }
  if (LOG.isDebugging()) {
    LOG.debugFine(nodeEntry + "set knn dist " + knnDist_node);
  }
  nodeEntry.setKnnDistance(knnDist_node);
}

private void preInsert ( MkMaxEntry q , MkMaxEntry nodeEntry , KNNHeap knns_q ) { if ( LOG . isDebugging ( ) ) { LOG . debugFine ( "preInsert " + q + " - " + nodeEntry + "\n" ) ; } double knnDist_q = knns_q . getKNNDistance ( ) ; MkMaxTreeNode < O > node = getNode ( nodeEntry ) ; double knnDist_node = 0. ; if ( node . isLeaf ( ) ) { for ( int i = 0 ; i < node . getNumEntries ( ) ; i ++ ) { MkMaxEntry p = node . getEntry ( i ) ; double dist_pq = distance ( p . getRoutingObjectID ( ) , q . getRoutingObjectID ( ) ) ; if ( dist_pq <= knnDist_q ) { knns_q . insert ( dist_pq , p . getRoutingObjectID ( ) ) ; if ( knns_q . size ( ) >= getKmax ( ) ) { knnDist_q = knns_q . getKNNDistance ( ) ; q . setKnnDistance ( knnDist_q ) ; } } if ( dist_pq <= p . getKnnDistance ( ) ) { KNNList knns_p = knnq . getKNNForDBID ( p . getRoutingObjectID ( ) , getKmax ( ) - 1 ) ; if ( knns_p . size ( ) + 1 < getKmax ( ) ) { p . setKnnDistance ( Double . NaN ) ; } else { double knnDist_p = Math . max ( dist_pq , knns_p . getKNNDistance ( ) ) ; p . setKnnDistance ( knnDist_p ) ; } } knnDist_node = Math . max ( knnDist_node , p . getKnnDistance ( ) ) ; } } else { List < DoubleIntPair > entries = getSortedEntries ( node , q . getRoutingObjectID ( ) ) ; for ( DoubleIntPair distEntry : entries ) { MkMaxEntry dirEntry = node . getEntry ( distEntry . second ) ; double entry_knnDist = dirEntry . getKnnDistance ( ) ; if ( distEntry . second < entry_knnDist || distEntry . second < knnDist_q ) { preInsert ( q , dirEntry , knns_q ) ; knnDist_q = knns_q . getKNNDistance ( ) ; } knnDist_node = Math . max ( knnDist_node , dirEntry . getKnnDistance ( ) ) ; } } if ( LOG . isDebugging ( ) ) { LOG . debugFine ( nodeEntry + "set knn dist " + knnDist_node ) ; } nodeEntry . setKnnDistance ( knnDist_node ) ; }
adapts the knn distances before insertion of entry q .
