-
Notifications
You must be signed in to change notification settings - Fork 0
/
evaluations.tex
217 lines (191 loc) · 8.31 KB
/
evaluations.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
\chapter{Experimental Evaluation}\label{c:evaluations}
We measured the runtime performance of our privacy\hyp preserving algorithms using the Sharemind secure computing platform.
We instantiated all private aggregators and decision tree classifiers using the SecreC programming language \cite{jagomagis2010secrec} that Sharemind provides.
In Sharemind, the number of the computing parties are restricted by the SMPC protocol that is been used.
Our experiments use the \textit{pd\_shared3p} security protocol, which utilizes three nodes in the private domain.
Below, we present the experimental evaluation timings of the developed privacy\hyp preserving histograms and decision trees.
Our goal is to provide a concise and holistic view of our experiments\footnote{All time measurements presented in this section correspond to the sole privacy computation. The importing timings were roughly 1 second, even for the largest dataset, thus we did not take it into account in the graphs.}, by carefully select the most descriptive diagrams.
\textbf{Experimental Setup:}
All experiments were performed on three 64-bit virtual machines (VM), each running Ubuntu 18.04.
The three VMs share an Intel Xeon E5-2670 (v2) at 2.50 GHz.
Each VM utilizes 6 cores and 8 GB of memory.
\section{Histograms}\label{s:results-histograms}
The first experimental timing results are about the privacy\hyp preserving histogram computations.
In figure \ref{chart:numerical-histogram} we show the scaling in execution time of histograms on numerical data.
In figure \ref{chart:categorical-histogram} we exhibit the respective measurements for histograms on categorical data.
\textit{Note:} both $x$ and $y$ axes are log\hyp scaled.
\begin{figure}[H]
\centering
\centerline{
\begin{minipage}{.5\linewidth}
\centering
\begin{tikzpicture}
\begin{axis}[
legend pos=north west,
scale only axis,
enlarge x limits=-1,
width=\textwidth*0.75,
ymajorgrids=true,
xmode=log,
ymode=log,
% log ticks with fixed point,
xlabel={Number of Patients},
ylabel={Time (s)},
ymin=0,
grid style=dashed
]
\addplot
coordinates {(100, 0.5)(1000, 3)(10000, 33)(100000, 355)};
\addlegendentry{1D}
\addplot
coordinates {(100, 2)(1000, 7)(10000, 68)(100000, 713)};
\addlegendentry{2D}
\end{axis}
\end{tikzpicture}
\caption{Numerical histograms timings}\label{chart:numerical-histogram}
\end{minipage}%
\begin{minipage}{.5\linewidth}
\centering
\begin{tikzpicture}
\begin{axis}[
legend pos=north west,
scale only axis,
enlarge x limits=-1,
width=\textwidth*0.75,
ymajorgrids=true,
xmode=log,
ymode=log,
% log ticks with fixed point,
xlabel={Number of Patients},
ylabel={Time (s)},
ymin=0,
grid style=dashed
]
\addplot
coordinates {(100, 0.2)(1000, 0.3)(10000, 3)(100000, 28)};
\addlegendentry{1D}
\addplot
coordinates {(100, 0.3)(1000, 2)(10000, 13)(100000, 131)};
\addlegendentry{2D}
\end{axis}
\end{tikzpicture}
\caption{Categorical histograms timings}\label{chart:categorical-histogram}
\end{minipage}
}
\end{figure}
One can observe that the histograms on categorical data perform better than their numerical data equivalents, especially when applied over bigger datasets.
This is due to the extra computation that needs to be done in the case of numerical data, in order to determine the corresponding histogram cell for each data tuple.
Moreover, the privacy\hyp preserving histograms scale linearly with the dataset size, regardless the type of it.
The chart below (figure \ref{chart:numerical-histogram-filters}) depicts the timings of histograms on numerical data (such as figure \ref{chart:numerical-histogram}), but also with the application of some filters\myslash constraints.
We can clearly see that as the dataset size grows, the number of filters does not make much of a difference in the total algorithm's execution time.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[H]
\centering
\centerline{
\begin{minipage}{.8\linewidth}
\centering
\begin{tikzpicture}
\begin{axis}[
legend pos=north west,
scale only axis,
enlarge x limits=-1,
width=\textwidth*0.75,
ymajorgrids=true,
xmode=log,
ymode=log,
% log ticks with fixed point,
xlabel={Number of Patients},
ylabel={Time (s)},
ymin=0,
grid style=dashed
]
\addplot
coordinates {(100, 0.6)(1000, 4)(10000, 34)(100000, 456)};
\addlegendentry{1D \& 1 Filter}
\addplot
coordinates {(100, 0.8)(1000, 4.2)(10000, 36)(100000, 480)};
\addlegendentry{1D \& 2 Filters}
\addplot
coordinates {(100, 2)(1000, 10)(10000, 86)(100000, 925)};
\addlegendentry{2D \& 1 Filter}
\addplot
coordinates {(100, 3)(1000, 11)(10000, 87)(100000, 929)};
\addlegendentry{2D \& 2 Filters}
\end{axis}
\end{tikzpicture}
\caption{Numerical histograms with filters timings}\label{chart:numerical-histogram-filters}
\end{minipage}%
}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Decision Trees}\label{s:results-dtrees}
Consecutively, we measured the privacy\hyp preserving classification algorithms.
Figure \ref{chart:id3-patients} portrays how the ID3 algorithm scales as the dataset size grows, for a constant number (3) of classification attributes (``Heart rate'', ``Height (cm)'' and ``Patient Age'').
C4.5 algorithm is more time consuming than ID3.
For reference, the training of the classification algorithm for 50 patients took about $13 * 10^3$ seconds, while for 100 patients the algorithm executed for $41*10^3$ seconds\footnote{For many classification attributes C4.5 has an unbearable runtime overhead, and for that reason we do not provide a corresponding chart as in the ID3 algorithm}.
\textit{Note:} both $x$ and $y$ axes are log\hyp scaled.
\begin{figure}[H]
\centering
\centerline{
\begin{minipage}{.5\linewidth}
\centering
\begin{tikzpicture}
\begin{axis}[
legend pos=north west,
scale only axis,
enlarge x limits=-1,
width=\textwidth*0.75,
ymajorgrids=true,
xmode=log,
ymode=log,
log ticks with fixed point,
xlabel={Number of Patients},
ylabel={Time (s)},
xtick = {50, 100, 200, 400, 800, 1600},
ytick = {400, 600, 800, 1200, 1600, 2400, 3200},
ymax=2500,
grid style=dashed,
y tick label style={/pgf/number format/.cd,%
set thousands separator={}},
x tick label style={/pgf/number format/.cd,%
set thousands separator={}}%
]
\addplot
coordinates {(50, 435)(100, 508)(200, 609)(400, 792)(800, 1240)(1600, 2090)};
\end{axis}
\end{tikzpicture}
\caption{ID3 decision tree classifier timings with variable patients for 3 attributes}\label{chart:id3-patients}
\end{minipage}%
\begin{minipage}{.5\linewidth}
\centering
\begin{tikzpicture}
\begin{axis}[
legend pos=north west,
scale only axis,
enlarge x limits=-1,
width=\textwidth*0.75,
ymode=log,
ymajorgrids=true,
% log ticks with fixed point,
xlabel={Number of Attributes},
xtick = {1, 2, 3, 4, 5},
ylabel={Time (s)},
ymin=0,
grid style=dashed
]
\addplot
coordinates {(1, 107)(2, 509)(3, 1547)(4, 3428)(5, 6835)};
\end{axis}
\end{tikzpicture}
\caption{ID3 decision tree classifier timings with variable number of attributes}\label{chart:id3-attributes}
\end{minipage}
}
\end{figure}
Finally, an overview of the runtime performance of the ID3 algorithm for a constant number of patients and variable number of classification attributes is presented in figure \ref{chart:id3-attributes}.\\ \textit{Note:} $y$ axis is log\hyp scaled.
As we observe from our experiments, the number of attributes used for classification is a dominating factor in the algorithm's performance.
The execution times for the privacy\hyp preserving creation of the decision trees is orders of magnitude greater than those of equivalent algorithms working on unencrypted data.
However, this is the training part of the classification algorithm which is performed offline.
For this reason, it does not affect the user experience, since training can happen non\hyp interactively at predefined periods of time (\textit{e.g.} every night or once a week).