a modification of nearest neighbor search

You might want to have a look at Geo::DNA for some useful techniques to aid in proximity searching. It encodes data into a DNA like string which then allows you to use stem-based searching to find nearest neighbours.