Caching Nearest Neighbors