Mobile Intelligence

11.5 CLUSTERING MOVING OBJECTS

Clustering is a technique for grouping a large number of objects and generates clusters, which are used to summarize the original dataset. There have been a lot of clustering algorithms proposed in data mining [25, 56]. In the following, we introduce some clustering techniques for moving object databases.

11.5.1 Continual Maintenance of Moving Clusters

Li et al. [36] proposed a real-time and adaptive cluster maintenance method for moving points. The approach is based on the notion of micro-clusters. A micro-cluster is a small-sized cluster consisting of nearby objects. After the generation of micro-clusters, some different clustering algorithms can be applied to the micro-clusters by treating each micro-cluster as if it were an individual entity. The idea of micro-clusters was initially proposed in BIRCH [69]. The method in Ref. [36] generates moving micro-clusters from the target moving objects, and then global clusters are generated using the micro-clusters. Since moving objects change positions and directions, the method maintains clusters adaptively.

The merging and partitioning processes for micro-clusters are performed using clustering features, which summarize the clusters. A clustering feature for a (micro-) cluster C_i is defined as

where t_i is the cluster generation time, n_i the number of elements (n_i = |C_i|), and sx_i (sy_i) the sum of the ...