Grid file with approximation: An improved approach for multi-dimensional nearest neighbor search

In this paper, we propose an approach to improve the grid file approach to the nearest neighbor (NN) search in multi-dimensional data spaces. The original approach is very efficient for low to medium dimensional database applications. However, its performance degrades when dimensionality becomes higher. In order to adapt the approach to higher dimensional databases, we build an approximation file based on the grid file. Then we first search the NN in the approximation file to filter out possible candidates before we actually go to the relative partition to pin down the true NN. By this way, the grid file approach is well adapted to higher dimensional databases. Our simulations show that the improved grid file approach outperforms other approaches in higher dimensional databases.