1
$\begingroup$

I am attempting to implement the T-DBSCAN algorithm described in T-DBSCAN: A Spatiotemporal Density Clustering for GPS Trajectory Segmentation. I have been able to implement most of the logic between the definitions (Page 3) and the pseudo-code (page 4), but I have not been able to implement the logic to determine if a cluster is a stop as described in Definition 9 of the paper (Page 3). Specifically, I am having trouble understanding Definition 7 "Temporally Continuous", which is referenced in Definition 9:

Definition 7. Temporally continuous (TC). Let the min and max time stamps of a cluster $C$ ($\subseteq D$) $ \text{mint} $ and $ \text{maxt} $, respectively. $ C $ is known as being “temporally continuous” if, for $ \forall{p_t \in D} $ and $ mint < t < maxt $, $ p_t \in C $.

where $ D $ is the trajectory, and $ p_t $ is a point at time $ t$.

As I read Definition 7, it sounds like it means that a cluster is temporally continuous if the points in the cluster are in the trajectory, and if all the timestamps of the point in the cluster is between the minimum time and maximum timestamp in the cluster, which doesn't make sense, because all points in a cluster will always be between the minimum and maximum timestamps in the same cluster, making all clusters temporally continuous.

Would someone be willing to point me in the right direction of how to interpret this section? Definition 9 logic is also not included in the pseudo-code, so I only have the definition itself to go off of.

I've read through an existing implementation on Github which does not have this logic implemented either, which leads me to believe either this section is trivial and does not need to be implemented, or that I am not the only one who has had issues implementing this last section of the algorithm.

Thanks for any help that you can provide. I'm willing to provide anymore information that I have that will be helpful.

$\endgroup$
1
$\begingroup$

Just to point out a minor confusion that there seems to be in the wording: there is mixed use of the the words temporarily and temporally. [OP has since corrected this]

We really only care about the final word, temporally i.e. relating to time, or the timestamps of the points in a cluster. Temporarily means only for a short period of time, which is a slightly different meaning to temporally' being related to time.

The way I understand the definition, a cluster is defined as a stop cluster if the minimum and maximum timestamps included that cluster ($mint$ and $maxt$)

Also, it seems definition 9 implies the usage of definition 7, so I would assume you need to implement it. If would be used a criterion as to whether a candidate cluster $C_i$ is defined as a stop cluster. So the final pseudo code would be something like:

stop_clusters = []    # empty list
for candidate in candidate_cluster:    # iterate over each stop cluster candidate 
    TC = cluster_is_tc(cluster)        # check cluster is Temporally Continuous
    TO = cluster_is_not_to(cluster)    # check cluster is Temporally Overlapping

    if (TC & TO):                      # if both criteria are met...
        stop_clusters.append(cluster)  # assign to stop clusters

How you implement those two check functions would be quite straight forward, according to the definition, assuming you have the timestamps of each point, you are trivially checking that all points are contained in the time bounds. Just skimming page 3, I am afraid the paper doesn't make these time bounds completely clear to me, but I hope it is clear to you as you are implementing it.

The same is true for the temporally overlapping criterion: you check that there is no overlap of timestamps in two clusters - if there is overlap (i.e. the intersection is not an empty set), then you cannot call the current candidate cluster a stop cluster.

Edit:

Looking at that implementation you linked, it could be that that are performing the check Temporally Overlapping check at this if line for the case of being non-overlapping and this else line for the other case that they do overlap in time (assuming there index values idx are the timestamps); they are checking that the largest timestamp is less than the minimum timestamp of the previous cluster.

I can't see evidence of the check for temporal continuity of a cluster.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.