A Density-Based Clustering of Spatio-Temporal Data - New Contributions in Information Systems and Technologies - page 39

Fig. 2. Illustration of locality in-between polylines (LIP) between trajectories, S and Q [8]

3 The Proposed Model

The following algorithm proposed in this study is inspired by TRACLUS, a spatial
algorithm that groups sub-trajectories using a modified DBSCAN technique and
GenSTLIP spatio-temporal function, a method which measures similarity of moving
objects considering their location and time of movement.

Notations: TR: a trajectory in set T

D: The set of sub-trajectories L formed
N Ɛ (L): The eps-neighborhood of a line segment
= ∈ | ,,,

Input: (1)Traj T={TR 1 ,TR 2 ,…TR n } (2) Ɛ (3)MinLns (4)K t (5)
Output: Clusters C = {C 1 ,C 2 ,…C n } and their representatives
for each (TR ∈ T) do /*Partitioning Phase*/
Partitioning of TR using MDL Principle
Get a set of L line segments, accumulate in set D
/*Grouping Phase*/
Execute Line Segment Clustering for set D
clusterId=0;
for each (L ∈ D) {
Compute N Ɛ (L);
if (|N Ɛ (L)| ≥ MinLns) then
Assign clusterId ∀ X ∈ N Ɛ (L)
Insert N Ɛ (L) - {L} into the queue Q;
ExpandCluster(Q,clusterId, Ɛ ,MinLns,k t , δ );
clusterId++;
else
Mark L as Noise }
ExpandCluster(Q,clusterId, Ɛ ,MinLns,k t , δ ){
While(Q ≠ 0) do
Compute N Ɛ (L);
if(|N Ɛ (L)| ≥ MinLns)
create new cluster}