header

### Program Information

Name: FindKNN
Domain: Machine learning
Functionality: To find k nearest neighbors of P(one m-dimensional test point) from S(n m-dimensional sample points).
Input:
$P=(p_{1},p_{2},\cdots,p_m)$:One m-dimensional test point(Type: Point) $S=(s_{1},s_{2},\cdots,s_n)$ where $s_i=(s_{i_{1}}s_{i_{2}},\cdots,s_{i_m})$:N m-dimensional sample points(Type: Set) k:A positive integer(Type: Integer)
Output:
$O=(o_{1},o_{2},\cdots,o_k)$ :Indices of the k nearest neighbors(Type: Index)

#### Reference

How Effectively Does Metamorphic Testing Alleviate the Oracle Problem? http://dx.doi.org/10.1109/TSE.2013.46

### MR Information

#### MR1

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f = S_s$ $k_f > k_s$
Output relation: $O_s \subset O_f$

#### MR2

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: The coordinates of $P_f$ = The coordinates of $P_s \times x$, where x is a non-zero real number. The coordinates of $S_f$ = The coordinates of $S_s \times x$, where x is a non-zero real number. $k_f = k_s$
Output relation: $O_f = O_s$

#### MR3

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f = S_s \cup \{P\}$ $k_f = k_s + 1$
Output relation: $O_f = O_s \cup \{n + 1\}$, where n+1 is the index of the added sample.

#### MR4

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f$ = Changing the order of $S_s$ $k_f = k_s$
Output relation: The indices of the selected k nearest neighbors of $O_f$ = Changing the indices of the selected k nearest neighbors of $O_s$ according to changing the order of samples.

#### MR5

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_{f_{1}},S_{f_{2}},k_f$ ; Follow-up output: $O_{f_{1}},O_{f_{2}}$
Input relation: $P_f = P_s$ $S_{f_{1}} \cup S_{f_{2}} = S_s$ $k_f = k_s$
Output relation: $O_s \subset O_{f_{1}} \cup O_{f_{2}}$

#### MR6

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ Each coordinate for each sample ${s^f}^i_l$ of $S_s$= Each coordinate $2p_l-{s^s}^i_l$ of $S_s$ $k_f = k_s$
Output relation: $O_f = O_s$

#### MR7

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f$ = Adding h<k points whose distance to P are not larger than that of the kth nearest neighbor to $S_s$. $k_f = k_s$
Output relation: $|O_s \cap O_f| = k – h$

#### MR8

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f$ = Adding some points whose distance to P are larger than that of the kth nearest neighbor to $S_s$. $k_f = k_s$
Output relation: $O_s = O_f$

#### MR9

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f$ = Deleting h<k samples from $S_s$. $k_f = k_s$
Output relation: $|O_s \cap O_f| \ge k – h$

#### MR10

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f$ = Adding another coordinate to $P_s$, where the value of the added coordinate is a constant. $S_f$ = Adding the same coordinate to $S_s$. $k_f = k_s$
Output relation: $O_s = O_f$

#### MR11

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f$ = Deleting some unselected samples from $S_s$. $k_f = k_s$
Output relation: $O_s = O_f$

#### MR12

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f$ = Deleting some selected samples from $S_s$. $k_f = k_s$
Output relation: $O_s \cap O_f = O_s \setminus$ {the indices of the deleted samples

#### MR13

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f$ = Adding a sample whose distance to P is smaller than the kth nearest neighbor to $S_s$. $k_f = k_s$
Output relation: $O_f = O_s \setminus \{ok \} \cup \{n+1\}$

#### MR14

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f$ = Changing the order of coordinates of $P_s$ $S_f$ = Changing the order of coordinates of $S_s$. $k_f = k_s$
Output relation: $O_f = O_s$

#### MR15

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: $P_f = P_s$ $S_f = S_s$. $k_f = k_s + 1$
Output relation: $O_f = (o^f_{1},o^f_{2},\cdots,o^f_k,o^f_{k+1})$ $O_s = (o^f_{1},o^f_{2},\cdots,o^f_k)$ $o^f_{k+1} \notin O$

#### MR16

Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
Input relation: The coordinates of $P_f$ = The coordinates of $P_s + x$, where x is a non-zero real number. The coordinates of $S_f$ = The coordinates of $S_s + x$, where x is a non-zero real number. $k_f = k_s$
Output relation: $O_f = O_s$

### Related

Insert title here