K-d Trees

k-d tree nearest neighbor search algorithm and explain about the k-d trees with an example
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures k-dTrees Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.k-d trees 2 k-d trees This may be a “KD” tree, but it is not a k-d tree http://www.kraft.com/k-d trees 5 k-d trees Used in image processing as a means of partitioning points in a k- dimensional space Binary search trees are excellent at storing and searching data 1- dimensional (i.e., linear) spacek-d trees 6 k-d trees As these examples demonstrate: – with binary trees, it is easy to find all points which fall inside a given interval (a 1d box) – how do we store points so that we can find all points which fall within a • rectangle (a 2d box), or • a 3d box?k-d trees 7 k-d trees To solve this problem, we will define a binary tree where st – depths 0, k, 2k, etc., contain binary search nodes sorted on the 1 coordinate – depths 1, k + 1, 2k + 1, etc., contain binary search nodes nodes sorted nd on the 2 coordinate, and in general – depths j, k + j, 2k + j, etc., contain binary search nodes sorted on the st (k + 1) coordinatek-d trees 8 k-d trees Comment on the naming convention: – while the k refers to the dimension, it is common to refer to such a tree as, for example, a 3-dimensional k-d tree instead of a 3-d tree, as numerous data structures could be referred to as 3-d trees k-d trees 9 k-d trees Given a set of points, we can construct a balanced k-d tree by always using the median element with respect the coordinate being searched on We will assume no duplication, but if duplication occurs, we can choose any of the median elementsk-d trees 10 k-d trees Suppose we wish to partition the following points in a 2-dimensional k-d tree: (0.03, 0.90), (0.37, 0.04), (0.56, 0.78), (0.01, 0.48), (0.41, 0.89), (0.95, 0.07), (0.97, 0.09), (0.54, 0.65), (0.04, 0.61), (0.73, 0.69), (0.46, 0.58), (0.08, 0.89), (0.04, 0.41), (0.94, 0.02), (0.33, 0.07), (0.55, 0.54), (0.06, 0.05), (0.04, 0.06), (0.74, 0.97), (0.29, 0.15), (0.05, 0.88), (0.23, 0.23), (0.55, 0.02), (0.02, 0.97), (0.05, 0.07), (0.06, 0.28), (0.09, 0.55), (0.02, 0.91), (0.05, 0.97), (0.68, 0.42), (0.97, 0.18)k-d trees 11 k-d trees st The first step is to order the points based on the 1 coordinate and find the median: (0.01, 0.48), (0.02, 0.91), (0.02, 0.97), (0.03, 0.90), (0.04, 0.06), (0.04, 0.41), (0.04, 0.61), (0.05, 0.07), (0.05, 0.88), (0.05, 0.97), (0.06, 0.05), (0.06, 0.28), (0.08, 0.89), (0.09, 0.55), (0.23, 0.23), (0.29, 0.15), (0.33, 0.07), (0.37, 0.04), (0.41, 0.89), (0.46, 0.58), (0.54, 0.65), (0.55, 0.02), (0.55, 0.54), (0.56, 0.78), (0.68, 0.42), (0.73, 0.69), (0.74, 0.97), (0.94, 0.02), (0.95, 0.07), (0.97, 0.09), (0.97, 0.18)k-d trees 12 k-d trees The median point, (0.29, 0.15), forms the root of our k-d treek-d trees 13 k-d trees This partitions the remaining points into two sets: (0.01, 0.48), (0.02, 0.91), (0.02, 0.97), (0.03, 0.90), (0.04, 0.06), (0.04, 0.41), (0.04, 0.61), (0.05, 0.07), (0.05, 0.88), (0.05, 0.97), (0.06, 0.05), (0.06, 0.28), (0.08, 0.89), (0.09, 0.55), (0.23, 0.23) (0.33, 0.07), (0.37, 0.04), (0.41, 0.89), (0.46, 0.58), (0.54, 0.65), (0.55, 0.02), (0.55, 0.54), (0.56, 0.78), (0.68, 0.42), (0.73, 0.69), (0.74, 0.97), (0.94, 0.02), (0.95, 0.07), (0.97, 0.09), (0.97, 0.18)k-d trees 14 k-d trees nd Starting with the first partition, we order these according to the 2 coordinate: (0.06, 0.05), (0.04, 0.06), (0.05, 0.07), (0.23, 0.23), (0.06, 0.28), (0.04, 0.41), (0.01, 0.48), (0.09, 0.55), (0.04, 0.61), (0.03, 0.90), (0.02, 0.91), (0.02, 0.97), (0.05, 0.88), (0.08, 0.89), (0.05, 0.97)k-d trees 15 k-d trees This point creates the left child of the root k-d trees 16 k-d trees Starting with the second partition, we also order these according to nd the 2 coordinate: (0.55, 0.02), (0.94, 0.02), (0.37, 0.04), (0.33, 0.07), (0.95, 0.07), (0.97, 0.09), (0.97, 0.18), (0.68, 0.42), (0.55, 0.54), (0.46, 0.58), (0.54, 0.65), (0.73, 0.69), (0.56, 0.78), (0.41, 0.89), (0.74, 0.97)k-d trees 17 k-d trees This point creates the right child of the root k-d trees 18 k-d trees st Next, ordering the partitioned elements by the 1 coordinate, we choose the medians to find the children of the left child (0.09, 0.55): (0.01, 0.48), (0.04, 0.06), (0.04, 0.41), (0.05, 0.07), (0.06, 0.05), (0.06, 0.28), (0.23, 0.23), (0.02, 0.91), (0.02, 0.97), (0.03, 0.90), (0.04, 0.61), (0.05, 0.88), (0.05, 0.97), (0.08, 0.89) k-d trees 19 k-d trees Doing the same with the two right partitions, we get the children of the right child of the root: (0.33, 0.07), (0.37, 0.04), (0.55, 0.02), (0.94, 0.02), (0.95, 0.07), (0.97, 0.09), (0.97, 0.18) (0.41, 0.89), (0.46, 0.58), (0.54, 0.65), (0.55, 0.54), (0.56, 0.78), (0.73, 0.69), (0.74, 0.97)k-d trees 20 k-d trees nd At the next level, we order the points again based on the 2 coordinate and choose the medians: (0.04, 0.06), (0.04, 0.41), (0.01, 0.48) (0.06, 0.05), (0.23, 0.23), (0.06, 0.28) (0.03, 0.90), (0.02, 0.91), (0.02, 0.97) (0.05, 0.88), (0.08, 0.89), (0.05, 0.97) (0.55, 0.02), (0.37, 0.04), (0.33, 0.07) (0.95, 0.07), (0.97, 0.09), (0.97, 0.18) (0.46, 0.58), (0.54, 0.65), (0.41, 0.89) (0.73, 0.69), (0.56, 0.78), (0.74, 0.97)k-d trees 21 k-d trees The remaining points fit in their appropriate locationsk-d trees 22 k-d trees The result is a 2-dimensional k-d tree of the given 31 points