An Efficient Grid Index for Moving Objects in Indoor Environments

With the advance in the indoor positioning systems such as RFID, WIFI, and Bluetooth, the locations of moving objects constitute a significant factor for many applications. Many researches have verified that most people spend their time in an indoor environment. In this paper, we propose two novel index structures, called Split Grid Index (SGI) and N-Density Split Grid Index (N-DSGI) for indexing moving objects in an indoor environment. SGI divides the grid into a set of cells when a new moving object enters. In particular, if a moving object moves into a grid cell, it is recursively divided into a set of smaller cells until each grid cell includes only one moving object. On the other hand, in N-DSGI, the grid is divided into a set of cells when (i) a new moving object enters the grid cell R and (ii) the number of moving objects in R exceeds the threshold value N. Through simulations, we verify that SGI and N-DSGI save CPU time while providing clients the valuable information.