Caching valid regions of spatial queries at mobile clients is effective in reducing the number of queries submitted by mobileclients and query load on the server. However, mobile clients suffer from longer waiting time for the server to compute valid regions.We propose in this paper a proxy-based approach to continuous nearest-neighbor (NN) and window queries. The proxy createsestimated valid regions (EVRs) for mobile clients by exploiting spatial and temporal locality of spatial queries. For NN queries, wedevise two new algorithms to accelerate EVR growth, leading the proxy to build effective EVRs even when the cache size is small. Onthe other hand, we propose to represent the EVRs of window queries in the form of vectors, called estimated window vectors (EWVs),to achieve larger estimated valid regions. This novel representation and the associated creation algorithm result in more effectiveEVRs of window queries. In addition, due to the distinct characteristics, we use separate index structures, namely EVR-tree and gridindex, for NN queries and window queries, respectively. To further increase efficiency, we develop algorithms to exploit the results ofNN queries to aid grid index growth, benefiting EWV creation of window queries. Similarly, the grid index is utilized to support NN queryanswering and EVR updating. We conduct several experiments for performance evaluation. The experimental results show that theproposed approach significantly outperforms the existing proxy-based approaches. A Proxy-Based Approach to Continuous Location-Based Spatial Queries in Mobile Environments