Over the years, there have been many attempts at improving the performance of nearest neighbor queries. This is an important endeavor because of the wide variety of uses of nearest neighbor searches, from geographic information systems (GIS) to databases to recommendation systems. An example is when a car is running low on fuel while driving; the GPS may be able to report the three closest gas stations to a cars [sic] current location.

This thesis provides the introduction of the Grid Variable Distance (GVD) approach of performing nearest neighbor searches that extends upon ideas of the iDistance approach of breaking up a d-dimensional area into a one-dimensional indexing scheme. Where iDistance has user determined reference points, GVD has reference points defined by the configurable dimension and subdivision. The GVD approach attempts to improve performance and I/O cost against other methods to make k-nearest-neighbor (kNN) processing faster and more efficient. The new approach is tested against both iDistance and R-Tree with uniform, normalized and real datasets. The results of the experiments show that the GVD approach processes queries faster with less I/O cost then both iDistance and R-Tree up to 14 dimensions.