private PriorityQueue < HeapItem > search ( final double [ ] target , double maxDistance , final int k ) { PriorityQueue < HeapItem > heap = new PriorityQueue < HeapItem > ( ) ; if ( root == null ) { return heap ; } double tau = maxDistance ; final FastQueue < Node > nodes = new FastQueue < Node > ( 20 , Node . class , false ) ; nodes . add ( root ) ; while ( nodes . size ( ) > 0 ) { final Node node = nodes . removeTail ( ) ; final double dist = distance ( items [ node . index ] , target ) ; if ( dist <= tau ) { if ( heap . size ( ) == k ) { heap . poll ( ) ; } heap . add ( new HeapItem ( node . index , dist ) ) ; if ( heap . size ( ) == k ) { tau = heap . element ( ) . dist ; } } if ( node . left != null && dist - tau <= node . threshold ) { nodes . add ( node . left ) ; } if ( node . right != null && dist + tau >= node . threshold ) { nodes . add ( node . right ) ; } } return heap ; }
Recursively search for the k nearest neighbors to target .