We show that we can do the search more efficiently by calculating a bounding envelope of the nearest-neighbour query region directly. Our solution is based on the observation that the weighted euclidean distance actually defines a transformation between spaces. The algorithms to calculate the bounding circle and bounding box of the query region directly from the weight matrix are provided. The time complexity of the algorithms are polynomial to the number of the dimensions and they are extensible directly to higher dimensional spaces. Using this approach, changes in the weight matrix can be handled easily with nominal computational overhead without having to rebuild the tree. We also provide an analytical and empirical results regarding the performance of our approach in terms of the number of disk pages touched.

Keys: nearest-neighbour search, weighted Euclidean distance, coordinate transformations, R-trees, spatial access methods