Four participants are sampled at random. We plot for each iteration, their own time-series with the closest perturbed centroid.

Current iteration : #0

Any individual obtaining the resulting set of common profiles, possibly helped by a user-friendly GUI, can use them for identifying those of particular interest. For example, in the tumor-growth use-case, Bob could benefit from the profiles that show an initial growth similar to his own time-series, but that is followed then by a steady decrease in size.

We show below the time-series of participant #213, say Bob, together with the profiles that are the closest to the sub-sequence that falls into the window (in grey). You can play with the window to select the sub-sequence that is used for similarity-matching. Extending the profiles matching with additional criterion is easy (e.g., largest distance with the complementary sub-sequence).

We illustrate the impact of the perturbation on the centroids quality by showing below the first four centroids, (1) at each iteration (2) before and after adding noise. We stress that we show them for illustrative purposes, the noise values never appear in the clear to any participant.

Four participants are sampled at random. We plot for each iteration, their own time-series with the closest perturbed centroid.

Current iteration : #0

The quality of a given clustering can be measured by a set of objective measures including the intra-cluster inertia. Intuitively, the intra-cluster inertia quantifies the relevance of a set of centroids to a dataset. It can be defined as the weighted squared sum of the distances between each data and its closest centroid (in our context, both are time-series). The figure below displays the evolution of the intra-cluster inertia of the perturbed centroids along the iterations of Chiaroscuro.

The operations performed by the Damgard-Jurik encryption scheme (the additively-homomorphic encryption scheme used in the current version of Chiaroscuro) consist in modular multiplications and modular exponentiations, which are computation-intensive operations. They are performed by personal devices when computing the candidate centroids at each iteration. The figures below show the average time (in seconds) spent by a participant in a complete iteration, at each iteration, for encrypting, decrypting, or adding candidate centroids. We measured times for three sizes of key (512 bits, 1024 bits, and 2048 bits) and on two personal devices (a current laptop and a decade-old laptop).

It is normal to observe times that decrease along the iterations because the number of centroids decreases monotonically. Indeed, the centroids that correspond to few data are strongly impacted by the differentially private perturbations, and become more and more irrelevant with respect to the actual data. They end up being "ejected" from the set of centroids. This phenomenon exists with non-perturbed k-Means, centroids that correspond to no data at all are also "ejected", but it is made stronger by differential privacy.

The homomorphic encryption also impacts the network traffic because it increases the size of the data exchanged. The figure below shows the average network traffic (in KB) per participant along the iterations for different key sizes (512 bits, 1024 bits, 2048 bits). We observe a steady reduction of the traffic due to the phenomenon of centroids loss described above.