An adaptive space split strategy for distributed processing of region monitoring queries

摘要

This paper addresses the problem of efficient processing of region monitoring queries, each of which continuously retrieves moving objects that currently locate within a given spatial query region. Traditional centralized methods for region monitoring queries assume that moving objects periodically send location-updates to the server, and that the server continuously updates the query results. However, such an assumption significantly degrades the system performance because of a huge amount of location-update stream. Recently, some distributed methods for region monitoring queries were proposed. In the distributed methods, the server assigns every moving object (i) a subspace of the workspace, referred to as the resident domain, and (ii) several nearby query regions. Each moving object sends a location-update to the server only when it leaves its resident domain or crosses any boundary of its query regions. For assignment of resident domains together with nearby query regions to moving objects, the distributed methods use the query indexing structures built by recursively splitting the workspace into equal halves. Unfortunately, these indexing structures suffer from a large number of unnecessary splits, which can result in a deterioration of the system performance. In this paper, to reduce the unnecessary splits, we propose a new adaptive split strategy, where the way of splitting the workspace is determined dynamically, taking into consideration of (i) the spatial relationships between the resultant subspaces and the query regions, and (ii) the distribution of query regions. We extend the Query Region tree (QR-tree) by applying the proposed split strategy. Through a set of simulations, we verify the efficiency of the proposed split strategy.