In multimedia database systems, the k nearest neighbor query occurs frerluently and requires the processing cost higher than other spatial queries do. The numberof searched nodes and the computation time in an index can be minimized for optimizing the cost of processing the k nearest neighbor query. In this paper, we propose the search distance which can reduce the computation time of the optimal search distance.