Mobile Intelligence

11.6 DENSE REGIONS AND SELECTIVITY ESTIMATION

A region on a space is called a dense region if the number of moving objects contained in the region is above some threshold. Detection of dense regions from the underlying moving object database is highly related to density-based clustering (described above). Dense region detection is also related to the estimation problem regarding query selectivity for moving object databases. Some dense region detection methods and query selectivity estimation techniques are briefly reviewed below.

11.6.1 Detecting Dense Regions

Hadjieleftheriou et al. [17] considered processing density-based queries on moving object databases. The density of region r during time interval Δt is defined as:

where n(r, t) is the number of objects inside r at time t and area(r) is the area of r. This definition of a dense region is intuitive, but tiny dense regions are also detected. To detect meaningful dense regions, they extend the above basic notion.

For example, a period density query is defined as follows. Given movement trajectories, a constant H, and thresholds α₁, α₂, and ξ, find regions {r₁,…, r_k} and associated maximal time intervals {Δt₁,…, Δt_k | Δt_i ⊂ [t_now, t_now + H]} such that α₁ ≤ area(r_i) ≤ α₂ and density(r_i, Δt_i) > ξ, where t_now is the current time. Some algorithms have been provided to find dense areas from a moving object database of linear movements ...