Abstract
Air indexing schemes of spatial data items have been researched for effective processing of spatial queries. However, the schemes cause the mobile clients to wait long for their desired items and to consume energy much. In this paper, we propose a new indexing scheme based on multi-leveled grid for window query processing on air. It allows fast and energy efficient processing of window query. Also, it has a linear structure matching the linear access pattern of the clients and makes them access only the queried data items. The simulations show that the proposed scheme outperforms the existing schemes in terms of access latency and energy efficiency.