CEDI: A Cell-based Distributed Index for Energy Conserving Range Query Processing on Air
Seokjin Im, Choi Jin Tag, Sangkeun Lee · The Journal of Korean Institute of Information Technology · 2008
This paper proposes Cell-based Distributed Spatial Index (shortly, CEDI) for effectively supporting range query in wireless data broadcast environment with spatial data. The proposed CEDI lets a client save the energy by listening to the only data contained within the given query window. The CEDI indexes the partitioned grid space and items in two-leveled scheme; the upper level index to the grid space with actual items, and the lower level index to items inside each cell in the grid space. Further, CEDI employs the concept of Implicit Data Pointing (shortly, IDP) to improve index search efficiency in the lower level index. The proposed CEDI has several nice properties: (1) considerably small index size, (2) table-formed linear structure suitable for linear access pattern of the client, and (3) multiple search paths by sharing links between distributed indexes. The simulation studies have been performed to evaluate the effectiveness of the proposed scheme. The result of simulation shows that CEDI can provide a significant performance improvement of energy consumption, while retaining low access latency.