Abstract 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...