Multi-dimensional Nearest Neighbor Search with Non-Uniform Data Sets

摘要

In this paper, we propose adapting grid file structure for nearest neighbor search in low to medium dimensional spaces. The approach is simple and the file is easy to construct and maintain. Previous experimental results showed that, with uniform distribution, it uses less CPU time and accesses fewer disk blocks man well-known structures, such as the SR-tree, VA-file, and the A-tree. We concentrate on a more realistic viewpoint by considering non-uniform distribution. From the results, the grid file is still the preferred structure for low to medium dimensional nearest neighbor search.