Animations of KD-tree searches

Andrew Moore

• Shows the levels of a kdtree, starting at the root and going down (Powerpoint) , (PDF) .
• Animation of range-search on a small dataset. Green rectangles denote nodes that require no searching. (Powerpoint) , (PDF) .
• Animation of range-search on the same dataset with a larger range. Obviously there are fewer savings since we visit all internal points. (Powerpoint) , (PDF) .
• Animation of range-search on a large dataset. (Powerpoint) , (PDF) .
• Animation of range-count on a small dataset (note internal prunes that Range Search cannot do) (Powerpoint) , (PDF) .
• Animation of range-count on a huge dataset (Powerpoint) , (PDF) .
• One-nearest neighbor search on a small dataset (Powerpoint) , (PDF) .
• Another one-nearest neighbor search on a small dataset (Powerpoint) , (PDF) .
• One-nearest neighbor search on a large dataset (Powerpoint) , (PDF) .

Other local KD-tree resources:

• A short tutorial on KD-trees
• Twenty-six papers on using kd-trees and related data structures within computational statistics, Machine Learning, Data Mining and AI