## 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 *α*_{1}, *α*_{2}, and *ξ*, find regions {*r*_{1},…, *r*_{k}} and associated maximal time intervals {Δ*t*_{1},…, Δ*t*_{k} | Δ*t*_{i} ⊂ [*t*_{now}, *t*_{now} + *H*]} such that *α*_{1} ≤ area(*r*_{i}) ≤ *α*_{2} 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 ...