Various arrangements for using a k-dimensional tree for a search are presented. A plurality of descriptors may be stored. Each of the plurality of descriptors stored is linked with a first number of stored dimensions. The search may be performed using the k-dimensional tree for one or more query descriptors that at least approximately match one or more of the plurality of descriptors linked with the first number of stored dimensions. The k-dimensional tree may be built using the plurality of descriptors wherein each of the plurality of descriptors is linked with a second number of dimensions when the k-dimensional tree is built. The second number of dimensions may be a greater number of dimensions than the first number of stored dimensions.