A Proxy-Based Approach to Continuous Location-Based Spatial Queries in Mobile Environments
Technology Used: Java/J2EE
Data Mining, IEEE 2013
Caching valid regions of spatial queries at mobile clients is effective in reducing the number of queries submitted by mobile clients and query load on the server. However, mobile clients suffer from longer waiting time for the server to compute valid regions. A proxy-based approach is proposed to continuous nearest-neighbor (NN) and window queries. The proxy creates estimated valid regions (EVRs) for mobile clients by exploiting spatial and temporal locality of spatial queries. For NN queries, two new algorithms is implemented to accelerate EVR growth, leading the proxy to build effective EVRs even when the cache size is small. EVRs of window queries is posed in the form of vectors, called estimated window vectors (EWVs), to achieve larger estimated valid regions. This novel representation and the associated creation algorithm result in more effective EVRs of window queries. In addition, due to the distinct characteristics, separate index structures are used, namely EVR-tree and grid index, for NN queries and window queries, respectively. The experimental results show that the proposed approach significantly outperforms the existing proxy-based approaches.
Basically, server-based approaches have the complete information of data objects and can utilize the information to create VRs for mobile clients.
LBS server creates the Voronoi diagram of data objects in an offline manner and returns the answer object of an NN query as well as the corresponding Voronoi cell to the querying client. The client caches the Voronoi cell to reduce the number of subsequent queries since the Voronoi cell is the VR of the answer object.
Proxy based approaches
Proxy-based approaches have only partial information of objects and exploit spatial and temporal locality of queries of mobile clients to build EVRs.
Slow growth of EVRs of NN queries
Slow growth of EVRs of window queries.
Lack of mutual support
Under Voronoi cell, searching the corresponding Voronoi cell is time consuming and object updates incur the overhead of partial reconstruction of the Voronoi diagram.
To propose proxy architecture as well as several companion algorithms to provide EVRs of NN and window queries on static data objects for mobile clients.
For NN queries, new algorithm is devised to efficiently create new and extend existing EVRs. The devised algorithms not only enable mobile clients to obtain effective EVRs immediately but also lead the proxy to build effective EVRs even when the proxy cache size is small.
For window queries, it is proposed to index the positions of data objects, instead of EVRs, by a grid index. It is proposed to represent the EVRs of window queries in the form of vectors, called estimated window vectors (EWVs), to achieve larger estimated valid regions.
Specifically, the grid index can be used to answer NN queries and extend existing EVRs.
The answer objects of NN queries are exploited to update the grid index, benefiting the creation of more effective EWVs of window queries.
Reduces the number of queries submitted by mobile clients
Reduces the time of obtaining query results and corresponding EVRs,
Reduces the load on the LBS server.
Introduce two index structures, an EVR-tree for NN queries and a grid index for window queries, due to the distinct characteristics of NN and window queries.