We propose in this paper a design of the proxy supporting nearest-neighbor queries. We also propose several algorithms to create and extend estimate valid regions. An estimate valid regions degradation algorithm and a cache replacement policy are proposed to reclaim cache space when the cache space is insufficient. To evaluate the performance of the proposed architecture and algorithms, several experiments are conducted. The experimental results show that the our design and algorithms are able to improve proxy hit rate and reduce average waiting time.