This paper presents an efficient branch-and-bound R-tree traversal algorithm for finding the k-nearest neighbors (k-NN) to a given point in space, a common query in Geographic Information Systems (GIS). The authors introduce two metrics—MINDIST and MINMAXDIST—to guide the search: MINDIST estimates the minimum distance from the query point to any enclosed MBR or object, while MINMAXDIST provides an upper bound on the minimum distance. The algorithm uses these metrics for ordering and pruning the search tree to reduce the number of nodes visited. Experimental results on both real-world and synthetic datasets demonstrate the effectiveness of the algorithm, showing that MINDIST ordering is more effective for spatially sorted data, while MINMAXDIST is more robust in dense regions. The paper also discusses the scalability of the algorithm and its performance with varying numbers of neighbors and data set sizes.This paper presents an efficient branch-and-bound R-tree traversal algorithm for finding the k-nearest neighbors (k-NN) to a given point in space, a common query in Geographic Information Systems (GIS). The authors introduce two metrics—MINDIST and MINMAXDIST—to guide the search: MINDIST estimates the minimum distance from the query point to any enclosed MBR or object, while MINMAXDIST provides an upper bound on the minimum distance. The algorithm uses these metrics for ordering and pruning the search tree to reduce the number of nodes visited. Experimental results on both real-world and synthetic datasets demonstrate the effectiveness of the algorithm, showing that MINDIST ordering is more effective for spatially sorted data, while MINMAXDIST is more robust in dense regions. The paper also discusses the scalability of the algorithm and its performance with varying numbers of neighbors and data set sizes.