Improving the performance of multidimensional search using fingers
Amalia Duch, Conrado Martı́nez · ACM Journal of Experimental Algorithmics · 2005
We propose two variants of K -d trees where fingers are used to improve the performance of orthogonal range search and nearest neighbor queries when they exhibit locality of reference. The experiments show that the second alternative yields significant savings. Although it yields more modest improvements, the first variant does it with much less memory requirements and great simplicity, which makes it more attractive on practical grounds.