## 4 Classification Based on Taxonomy and Design Drivers
### Similarity Search  
In SDS [19], described in Section 3.2, a data item denoted by \(d\) consists of keywords denoted by \(v^{d}\). Thus, the data item \(d\) is represented by \(d=(v_{i}^{d},\ v_{i}^{d},........,v_{n}^{d})\). For a similarity search, the following formula is proposed in SDS to calculate the similarity between data items \(d_{l}\) and \(d_{2}\):  
\[Similarity=\frac{\sum\limits_{i=1}^{n}w_{i}*B(v_{i}^{d1},v_{i}^{d2})}{\sum \limits_{i=1}^{n}w_{i}} \tag{13}\]  
Here, \(m\) is the number of attributes, \(w_{i}\) is the weight for each attribute based on their significance as shown in Table 2 and _B(i, j)_ is a Boolean function returning 1 if \(v_{i}^{d1}\)=\(v_{i}^{d2}\) and 0 otherwise. For example, a data item in a WSN application is characterized by five attribute lists such as object, model, color, direction and division with the weight value shown in Table 2. Consider the following two data items denoted by \(d_{l}\) and \(d_{2}\):  
\[d_{i}=\big{(}Plane,F-16,Blue,Northwest,Airforce\big{)}\] \[d_{i}=\big{(}Plane,F-16,White,Southwest,Airforce\big{)}\] \begin{table}
\begin{tabular}{c c c} \hline \hline
**Attribute** & **Keywords** & **Weight** \\ \hline Object & Car, Plane, Truck, _etc._ & 0.3 \\ Model & F-16, F-17, _etc._ & 0.2 \\ Color & Red, Purple, etc & 0.1 \\ Direction & North, South, etc & 0.1 \\ Division & Air-Force, _etc._ & 0.1 \\ Pressure & Integer & 0.1 \\ Speed & Float & 0.1 \\.. &.. &.. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Example of Weight Settings [19]. \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Mechanisms** & **Schemes** \\ \hline \multirow{4}{*}{Tree Structure} & Bit Code Mapping & MDA [35] \\  & Multiply Rooted Hierarchical Index & DIFS [30] \\  & Binary Tree & DIM [13] \\  & Others & SSA [22] \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of Range-Query Data-Centric Storage (DCS) Schemes. Hence,  
\[Similarity_{s,t,2}=\frac{0.3*1+0.2*1+0.1*0+0.1*0+0.1*1}{0.3+0.2+0.1+0.1+0.1}=0.75\]  
SDS uses Locality-Sensitive Hashing (LSH) [37] to transform \(d\) to a series of hash values. Using LSH, data items that have common keywords will have the same hash value while similar data items will have similar hash values. For example, if the difference between \(d_{I}\), \(d_{2}\), and \(d_{3}\) is \(d_{I}>d_{2}>d_{3}\), their hash values conform to \(h_{d1}>h_{d2}>h_{d3}\), where \(h_{d}\) is the hash value of d. A data item with a hash value \(h\) is mapped to the first zone with \(ID\geq h\). For example, if the value of \(h_{d1}\) returned by LSH is five, then the value of \(h_{d2}\) (\(d_{I}\) and \(d_{2}\) refer to the data item shown above) would approximately be 6.67 or 3.75. Hence, \(d_{I}\) will be stored in the zone with \(ID\geq 5\) and \(d_{2}\) will be stored in the zone with \(ID\geq 3.75\) or \(ID\geq 6.67\). Thus, a query denoted by \(d_{q}\) with 80% similarity will search in zones with IDs: \(\sqrt[4]{5}\cdot h_{s_{i}}\leq h_{s_{i}}\leq 5\sqrt[4]{4}\cdot h_{s_{i}}\). In SSA [22], referring to Section 3.3, when data is queried, the query is first sent to the specific cell, with the range of this cell in the queried data. The SSA similarity search mechanism contains two phases known as the similarity search query resolving phase and the query probing phase. The query resolving phase determines an indexing node that is most likely to provide an answer for the query. If the answer does not match exactly then the query probing phase is initiated to find the closest possible answer. In the query resolving phase, the function _locate_ (\(V_{q}\)) is used to find the target node \(I_{T}\) with the indexing node \(I_{ID}\) such that \(R_{L}+(I_{ID}-1)\cdot r\leq V_{q}<R_{L}+I_{ID}r\), where \(V_{q}\) is the search value given by the query. The query is then forwarded to the Target Node \(I_{T}\) to retrieve data. If an exact match to \(V_{q}\) is found, then the query execution is finished, otherwise the query probing phase comes in action.