Partially specified nearest neighbor searches using k-d trees

A partially specified nearest neighbor query is a nearest neighbor search in which only some of the possible keys are specified. An algorithm that uses k-d trees to perform such searching is described. The expected time complexity is O(N^{1-$\text{j}\text{k}$}). where k is the total number of keys and j the number of keys specified in the query. Experimental results, which are consistent with the theoretical predictions, are also presented.