## 4 Experimental Setup
In the case that for a query, more than \(k+1\) targets remained in this classification, we used all of them for searching for the \(k\)-nearest neighbors, but put an additional termination criterion if the number of structures after two or more iterations of pairwise dominance exceeds a given number. This effects only about a dozen queries that needed an extremely long run time for \(k=10\). If this termination criterion is applied, we do not obtain an exact classification, but shorter run times. ```
1:\(q\)// Query structure. 2:\(\mathcal{T}\)// Set of target structures. 3:\(R_{F}\)\(\forall F\in\mathcal{C}\)// Family representatives; see Equation (4). 4:\(d(A,R_{F})\)\(\forall A\in\mathcal{F}\) for all families \(\mathcal{F}\in\mathcal{C}\)// Distance from all family members to the respective representative. 5:\(\underline{d}(q,R_{F})\), \(\overline{d}(q,R_{F})\)\(\forall F\in\mathcal{C}\)// Bounds on the distance from the query to the family representatives. 6:LB \(\leftarrow\)\(\{(t,-\infty)|t\in\mathcal{T}\}\)// Priority queue, which will hold the targets \(t\) in the order of increasing lower bound distance \(d_{\triangledown}(q,t)\) to the query. 7:UB \(\leftarrow\)\(\{(t,\infty)|t\in\mathcal{T}\}\)// Priority queue, which will hold the targets \(t\) in the order of increasing upper bound distance \(d^{\triangle}(q,t)\) to the query. 8:\(t_{\text{\emph{{\tiny UB}}}}^{\text{\emph{UB}}}\)//A pointer to the \(k\)-th element in UB
9:\(\tau\)\(\leftarrow\)\(1\)// Time limit for pairwise alignment. 10:for\(\mathcal{F}\in\mathcal{C}\)do
11: FAM\([\mathcal{F}]\)\(\leftarrow\)\(|\{t\in\mathcal{T}:t\) belongs to family \(\mathcal{F}\}|\)// Number of family members. 12:endfor
13:while\(\exists R_{\mathcal{F}}:\underline{d}(q,R_{\mathcal{F}})\
eq\overline{d}(q,R_ {\mathcal{F}})\) and \(|\mathcal{T}|\) changes do
14:\(\tau\)\(\leftarrow\)\(\tau\)\(\times\)\(2\)
15:for\(\mathcal{F}\in\mathcal{C}\) with FAM\([\mathcal{F}]>0\)do
16: Recompute \(\underline{d}(q,R_{F})\) and \(\overline{d}(q,R_{F})\) using time limit \(\tau\)
17:for\(t\in\mathcal{F}\)do
18: Update priority of \(t\) in LB to \(d_{\triangledown}(q,t)=|\underline{d}(q,R_{F})-d(R_{F},t)|\). // Bound from inverse triangle inequality Equation (7). 19: Update priority of \(t\) in UB to \(d^{\triangle}(q,t)=\overline{d}(q,R_{F})+d(R_{F},t)\). // Bound from triangle inequality Equation (6). 20:endfor
21:endfor
22:// Check for targets dominated by \(t_{\text{\emph{{\tiny UB}}}}^{\text{\emph{UB}}}\). 23:for target \(t\) in \(\mathcal{T}\)do
24:if\(d_{\triangledown}(q,t)>d^{\triangle}(q,t_{\text{\emph{{\tiny UB}}}}^{ \text{\emph{UB}}})\)then
25:\(\mathcal{T}\leftarrow\)\(\mathcal{T}\setminus t\)
26: LB \(\leftarrow\) LB\(\setminus t\)
27: UB \(\leftarrow\) UB\(\setminus t\)
28: FAM\([\mathcal{F}]\)\(\leftarrow\) FAM\([\mathcal{F}]-1\) where \(\mathcal{F}\) is the family of \(t\). 29:endif
30:endfor
31:if\(|\mathcal{T}|=k\)then
32:return The majority superfamily membership \(\mathcal{S}\) among \(\mathcal{T}\). 33:endif
34:endwhile
35:Apply the dominance protocol for query \(q\) and targets \(t\in\mathcal{T}\) as described in [9]. (The quality of the bounds \(\underline{d}(q,t)\) and \(\overline{d}(q,t)\) are improved by stepwise incrementing \(\tau\) within the given time limit. At each step, the direct dominance (Lemma (4)) is applied for the targets from the updated \(\mathcal{T}\).) ```  
**Algorithm 1** Solving the \(k\)-NN classification problem