Due to the personal portable devices and advances in wireless communication technologies, Location Dependent Information Services (LDISs) have received a lot of attention from both the industrial and academic communities.In LDISs,it is important to reduce the query response time, since a late query response may contain out-of-date information.In this paper, we study the issue of LDISs using a Voronoi Diagram.We introduce a new NN search method, called the Exponential Sequence Scheme (ESS), to support NN query processing in periodic broadcast environment.This paper aims to provide research directions towards minimizing both the access latency and energy consumption for the NN-query processing.