dm.cs.tu-dortmund.de/en/mlbits/class-knn-accelerating/
Accelerating k Nearest Neighbors – Lecture Notes
R_3), (2.7, p_1), (2.9, p_3), (3.6, p_2)]\)
Expand leaf node \(R_1\)
\(Q=[(1.6, p_6), (2.0, p_5), (2.2, R_3), (2.7, p_1), (2.9, p_3),\) …
Found \(p_6\)
\(Q=[(2.0, p_5), (2.2, R_3), (2.7, p_1), (2.9, p_3), [...] the \(k=2\) nearest neighbors:
\(Q=[(0, R_0)]\) initial queue with root node
Expand directory node \(R_0\)
\(Q=[(0.7, R_2), (1.2, R_1), (2.2, R_3)]\)
Expand leaf node \(R_2\)
\(Q=[(1.2, R_1), (2.2, R_3) [...] (3.6, p_2),\) …
Found \(p_5\) , set threshold \(\tau =2.0\)
\(Q=[(2.2, R_3), (2.7, p_1), (2.9, p_3), (3.6, p_2), (4.1, p_7)]\)
Stop (no other point at same distance possible)
Note: we never processed …
