MLAIN: Multi-leveled air indexing scheme in non-flat wireless data broadcast for efficient window query processing

In ubiquitous computing, it is critical to allow a great number of clients to access information simultaneously at any place and at any time. Wireless data broadcasting provides effective information services due to its own high scalability. In this paper, we propose a novel indexing scheme for spatial data items that adopts multi-leveled grid partition to support window queries in non-flat data broadcasting that considers clients' skewed data access patterns. In the proposed scheme, each cell of the partition is restricted to its number of data items. This constraint makes the proposed scheme different from other schemes that use a space partition. Cell indexes of cells that keep link information between cells are interleaved with data items on the channel. The scheme allows clients to access queried data items quickly by reducing the broadcast cycle and the spacing between indexes, and providing multiple paths to a cell on the channel. We show the efficiency of the proposed scheme with regard to the access time, tuning time, and energy consumption using intensive simulation studies.