# Hadoop vs. Spark: Impact on Performance of the Hammer Query Engine for Open Data Corpora
## 5 The _Hammer_ Prototype
### Step 4/5 Executor: Basic Algorithm  
Algorithm 1 reports the pseudo-code of the algorithm implemented within the _Step4/5 Executor_. The procedure is divided in two parts: in the first part, the set of data sets that satisfy at least one query \(nq\in Q\) (the set of queries to process) is generated; in the second part (line 4), the final set of data sets is generated, such that their relevance measure \(rn\) is greater than the minimum threshold \(th\_rm\). ```
Procedure Step4/5_Executor(\(Q\), \(th\_krm\), \(th\_rm\)) begin
1. MongoDB_Clear_FoundDS()
2. For Each \(q\in Q\)do
3. Process_Query(\(q\), \(th\_krm\)) End For Each
4. Evaluate_RM() End Procedure
```  
**Algorithm 1**Algorithm for Step 4. The main data structure we adopt in the algorithm is the data set descriptor  
\[ds:(\texttt{ds\_id},\texttt{W}:[(\texttt{t},\texttt{w})],\texttt{krm}, \texttt{r}\texttt{m},q),\]  
where ds_id is the data set identifier. W is a vector of term weights, where each element is a pair that associates a term t with its weight w (to compute the cosine similarity with respect to a query). krm is the keyword relevance measure (obtained by applying the VSM approach); rm is the best relevance measure and \(q\) is the query for which the best relevance measure is obtained. We now present the algorithm in detail:  
* At line 1, function **MongoDB_Clear_FoundDS** is called. It resets the content of a _MongoDB_ collection called **FoundDS**: this collection has to store data set descriptors that satisfy at least one query \(q\in Q\). * The **For Each** loop on line 2 calls (line 3) procedure **Process_Query** for each query \(q\in Q\). This procedure stores data set descriptors possibly found for query \(q\) in the _MongoDB_ collection **FoundDS**. Figure 3: General architecture of the _Query Engine_. * Algorithm 2 reports the pseudo-code of procedure **Process_Query**, which actually implements Step 4, for each single query \(q\in Q\). We now describe its work in detail:
* The procedure receives a query \(q\) and the minimum threshold for the keyword relevance measure \(th\_krm\). * On line 2, the set \(DS\) of data set descriptors is set to be empty. Furthermore, on line 3, function **MongoDB_Get_FoundDS*
* gets the set of data set descriptors already found for previous processed queries in \(Q\). * The **For Each*
* loop on line 4 iterates for each term \(t\) in the set of terms \(q\_terms\) extracted for query \(q\) by _Step 3 Executor_. In particular, for each term \(t\), the loop queries the inverted index stored within a _MongoDB_collection: function **MongoDB_DS_for_term_Except*
* queries the inverted index and returns the set of data set descriptors that contain term \(t\); however, data sets already present in collection **FoundDS*
* are not retrieved by the function, in order to optimize the process: in fact, if a data set has been already found by a previous query, there is no need to consider it again in Step 4. Specifically, the **If*
* instruction on line 5 assigns the content of the set of data set descriptors retrieved from the inverted index directly to \(DS\) if \(DS\) is empty (for the first processed term); otherwise (**Else*
* branch on line 7), the new set of data set descriptors retrieved from the inverted index is intersected with the previous one. Only data sets common to both operands of \(\cap\) have a descriptor in its output: consequently, \(DS\) progressively narrows at each iteration. Finally, line 8 checks if the set \(DS\) is empty: if this happens, it means that no data sets satisfying the query are in the corpus. * Once completed the first **For Each*
* loop, it is necessary to evaluate the keyword relevance measure for each data set in \(DS\). Line 9 sets to empty the set of selected data sets \(selectedDS\). * The loop on line 10 actually makes the computation of the keyword relevance measure \(krm\) for each data set in \(DS\). On line 11, the cosine similarity between terms in data set \(ds\) (vector \(\mathtt{W}\)) and terms in the query \(q\) is computed (by function **CosineSimilarity**).