Spatial Query Processing In Wireless Broadcast Environment

With the popularity of mobile devices, the development of mobile computing and global positioning technologies, spatial query processing becomes more and more important in our daily life. The spatial query processing techniques are widely used in personal trip planning, intelligent transportation systems, emergency, location-based advertisements, and location-based social networks.Traditional spatial query processing techniques are in point-to-point model. In this model, mobile users send their locations and queries to the server, and the server processes the queries and returns the results to users. Another model to implement spatial queries is wireless broadcast model. In this model, the server repeatly broadcasts the spatial data to users. The user tunes into the broadcast channel to read interesting data and process the query locally after getting the data needed. The wireless broadcast model is more scalable, and is suitable for system where there are large amount of users. Another advantage of this model is that the location privacy of mobile users is not leaked to the server.This paper addresses the shortest path query, proximity query, and spatial keyword query in wireless broadcast environments. Firstly, a novel air index for shortest path computing, namely BagIndex, is proposed. Secondly, an air index for proximity query processing in road networks, namely NPI, is proposed. This index is based on grid partition on road networks, and supports common proximity queries such as range query, kNN query, and CNN query. Next, an air index named IRGI, which is an integration of grid index and inverted files, is proposed for spatial keyword searching in wireless broadcast environments. Finally, all proposed techniques’s performance is evaluated with real road networks.