KD-Tree and LSH

1. K Nearest Neighbours: Linear Scan

2. Speed of KNN

3. Improvement over KNN: KD-Tree

4. Split the Data into Two Groups

5. The Constructed KD-Tree

6. Query a KD-Tree

7. The Nearest Neighbour in Node 3

8. Traverse One Level Up to Node 1

Whether we need to check the nodes 1 All remaining data points in ？
We can include all by checking
node 4 Whether the point of is closer than the current near point .

9. Nearest Neighbour Updated

10.Traverse One Level Up to Root

Whether we need to check the nodes 2 All remaining data points in ？
We can include all by checking
node 2 Whether the point of is closer than the current near point .