list of results is initially empty

for each image j in the database
{
     dist = D(vj ,vq)
     if (#results < k or dist < maxD)
     {
          insert (j,dist) into results
          sort results by dist
          maxD = largest dist in results
     }
}

Cost   =   T_open  +  N_PT_P  +  NT_D

Note: If q is an image from the database, we can use a pre-computed distance table to make this much faster.