If you're wondering what distributed expectation-based spatio-temporal clustering is, it's not as terrifying as it sounds. Honest!

Spatio-temporal clustering is a way of partitioning data in space and time. Simply put, spatio-temporal clustering is the partitioning of data points which share similar characteristics, including time, into clusters.

In contrast, spatial clustering algorithms only group items based on spatial characteristics such as geographic location. For example, imagine that the red lines in Figure 1 below represent face to face conversations between people labelled 0, 1, 2, all the way up to 35. Then we could extract a cluster of from this data, i.e., all the people who have spoken to other people - but this tells us nothing about when the people spoke.

Figure 1. Some data that has been clustered using a spatial algorithm.

Figure 1. Some data that has been clustered using a spatial algorithm.

Now imagine that the data is split into a number of time frames, and graphs such as the one shown in Figure 1 are created for each time frame. Figure 2 shows the graphs generated in the 4th, 5th, and 6th hours of the same dataset that was used in Figure 1. The only difference is now we can see some temporal information. It is now easy to imagine that spatial clusters can be extracted in each of the three time frames, and each spatial cluster will be linked to a particular time frame, thus creating spatio-temporal clusters.

4th hour.5th hour.6th hour.

Figure 2. The 4th, 5th, and 6th hours of the same dataset as was shown in Figure 1, showing a different spatio-temporal cluster in each time frame.

An area where spatio-temporal clustering may be useful, is in distributed systems such as Pocket Switched Networks (PSNs). Distributed clustering algorithms tend to generate spatial clusters. Distributed clustering algorimths that generate clusters over a over long periods of time, with no regard for temporal information, are called aggregated clustering algorithms. Furthermore, if information is only added and not later removed from aggregated clusters, the end result is called aggregated monotonic clustering.

In order that personal mobile devices such as smartphones can detect spatio-temporal clusters using short range wireless communications like Bluetooth, we proposed Distributed Expectation-Based spatio-Temporal (DEBT) clustering. DEBT works using software installed on smartphones which can detect when some measure of connectivity with other smartphones is greater than what it expected. Also included in the paper are some opportunistic routing algorithms for PSNs which utilise DEBT clusters. If you're interested in exactly how we did this, you can read the paper. Or, if you'd like to try out DEBT for yourself you can download the DRAFT and DEBT code bundle for The ONE simulator with example config files from this link.