## 5 Dynamis Service Selection
### Dynamis: Histogram, ART, Top k and Skyline  
Dynamis addresses the aforementioned problems of null and fluctuating values effectively. Rather than taking an instantaneous measurement of each attribute, we collect the \(\
u\) most recent measurements in a histogram. In this case, null values only become a concern when all of the last \(\
u\) measurements are null, at which point, it can safely be assumed that there is something significantly wrong with the property. Neither aggregation nor skyline are defined for histograms (_i.e._, collections of measurements). A natural approach is to define a function on a histogram to convert it into a sensible value. We use the area-right-of-threshold (_ART_ ) function, for this purpose. Specifically,  
\[Area=ART_{s}(A_{i},\tau_{i})\]  
is the number of measurements for service \(s\) for attribute \(A_{i}\) that are greater than threshold \(\tau_{i}\). The intuition for the area-right-of-threshold comes from the idea of integrating in service selection the most important part of the histogram. Now, we specify both the aggregation and the skyline problems on histograms. The top \(k\) histogram aggregation problem is to retrieve from the set of services \(\mathbb{S}\), with attributes:  
\[\mathbb{A}=\langle A_{1},\ldots,A_{m}\rangle\]  
given a weight vector:  
\[\vec{w}=\langle w_{1},\ldots,w_{m}\rangle\]and a threshold vector:  
\[\vec{\tau}=\langle\tau_{1},\dots,\tau_{m}\rangle\]  
the top \(k\) ranked services with respect to aggregation function:  
\[\sum_{i=1}^{m}w_{i}\cdot ART_{s}(A_{i},\tau_{i})\]  
Instead of considering snapshot values for an attribute \(A_{i}\), we compute \(ART_{s}(A_{i},\tau_{i})\) from \(A_{i}\)'s histogram (_cf._, Algorithm 1). ```
1:Inputs a set \(S\) of functionally equivalent web services;
2:\(a\) set \(\mathbb{A}\) of dynamic attributes for each service;
3:\(a\) threshold vector \(\vec{\tau}\) where \(\tau_{i}\) is a threshold for attribute \(A_{i}\);
4:\(a\) weight vector \(\vec{w}\) where \(w_{i}\) is a weight for attribute \(A_{i}\) (i.e.,context);
5:\(a\) time \(t\) where the evaluation takes place;
6:\(a\) time window \(\
u\) over which attributes are considered;
7:\(a\) scalar \(k\) to indicate the number of services to return. 8:Output The top \(k\) services with respect to context \(\vec{w}\)
9:Procedure DynamisAggregation(\(S,\mathbb{A},\vec{\tau},\vec{w},t,\
u,k\))
10:for each \(s\in S\)do
11:\(Score[s]\gets 0\)
12:for each \(A_{i}\in\mathbb{A}\)do
13:\(h\leftarrow\operatorname{Histogram}(A_{i},t-\
u,t)\)
14:\(Area\gets ART(h,\tau_{i})\)
15:\(Score[s]\gets Score[s]+w_{i}\times Area\)
16:endfor
17:endfor
18:\(Dynamis\leftarrow\operatorname{Sort}(Score,>)\)
19:return\(Dynamis[1:k]\)\(\triangleright\) return the top \(k\) tuples
20:endProcedure
```  
**Algorithm 1** Dynamis aggregation. Since the result of the skyline is not ranked, we employ the notion of \(k\)-dominance introduced by [PERSON] _et al_. [29]. Thus, we compute a score for each service as follows. Suppose \(\langle a_{1},\dots,a_{n}\rangle\) is the tuple of attribute values of service \(s\) in its skyline. We now consider the sorted lists of values for each of these attributes considering the services in its skyline. For each value \(a_{i}\), we check to see what its rank is in the sorted list. By \(r_{i}\), we denote the rank of \(a_{i}\) in the list. Let \(r_{s}=\langle r_{1},\ldots,r_{m}\rangle\) be the vector of the ranks for \(s\). Then, the scoring function simply sums up these ranks as follows. \[\mathsf{Score}(h)=\sum_{i=1}^{m}\mathsf{Rank}_{i}(h)=\sum_{i=1}^{m}r_{i}.\]  
Finally, we retrieve the top \(k\) services from the skyline according to this scoring function (_cf._, Algorithm 2).