Effective Density Queries of Continuously Moving Objects

In this paper, we study a newly emerging type of queries on moving objects - the density query. Basically, this query locates regions in the data space where the density of the objects is high. This type of queries is especially useful in Location Based Services (LBS). For example, in a traffic control system, we need to identify the places that are or would be affected by a traffic jam, and report this information to drivers so that they can choose a less congested route. As a naive way to solve the problem is prohibitively expensive, we first introduce a framework which makes the problem manageable. Then we propose efficient algorithms to realize this framework based on the Bx-tree index. Our extensive experimentation proves the efficiency of our algorithms.