results = [];   maxD = infinity

for each obj in the database
{
	dist = D(vobj,vq)
	if (#results < k or dist < maxD)
	{
		insert (obj,dist) into results
		// results is sorted with length <= k
		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.