KD-Tree Nearest Neighbor Data Structure

[@benwu4583]

50 min lecture material wrapped in a 7 min video. Honestly amazing!

[@yashagarwal8249]

In 6 and a half minutes, you managed to teach me the fundamentals of something I thought would take a lot of time. Amazing, thank you!

[@wonton1019]

This is the greatest visualization of nearest neighbors I've ever seen. You sir, are a blessing beyond words, I'm not religious but I might as well be after watching your video. Thank you.

[@stablesort]

Thanks for such a great compliment! I am happy to hear that the video resonated with you so much!

[@SauravSahu01]

Same here. I have never seen such teacher. He is GOD level.

[@arnavanuj]

One of the most useful searching algo in data science

[@stablesort]

Definitely a good one to know. I have seen it pop up in interviews as well.

[@maridavies3425]

Awesome tutorial on KDtree data structure! The nearest neighbor search algorithm is easy to follow here. Thanks, keep em coming!

[@stablesort]

Thanks for the compliment! More tutorials are on the way =)

[@Aca99100]

This tutorial was very precise, direct and comprehensive and it really helped me understand how to use kd trees. Thank you so much sir!

[@stablesort]

You are very welcome!

[@1230986666]

This video hits all the right notes: short, useful and clear. Keep up the excellent work!

[@maxinteltech3321]

Great visualization of a complex concept

[@mukulbhave]

simple ,short and precise. Awesome

[@omarshawky5859]

I came to you from 2 independent great courses not understanding a specific scenario where they ignore an entire section without clarifying the reason but you explained it extremely better than both; Well done! Thank you :)

[@stablesort]

thanks for leaving a few good words!

[@NoName-ip4tt]

This is an interview question. How to design an algorithm for a flight computer to find closest airport during the flight in an emergency? Well explained along with lucid diagrams... Thanks for sharing your knowledge...

[@familytamelo8140]

Concise and yet very informative. Enjoyed. Thanks!

[@stablesort]

Thanks for the compliment! Glad to know that it was helpful.

[@papayasprout]

This cleared up k-d Trees for me. Thanks for putting up the video.

[@zafirr1]

Nice explanation, I have a question though. Since this is not a balanced binary search tree, the worse case is still O(n) right? Or is there a way to use balancing techniques (like in a treap) with kd trees?

[@stablesort]

Excellent question and you are right on the money - KD-Tree has the potential to be heavily unbalanced, which results in O(n) search. The simplest approach to ensure a balanced (statistically speaking) tree that I could think of, in the case where all of the points are specified at the start, is to just shuffle the points before constructing the tree. But there are more sophisticated techniques that pick a good median value on each insertion. Also check out KDB-Trees (en.wikipedia.org/wiki/K-D-B-tree) they are balanced by design. Alternatively, if you have lots of inserts and deletes to a KD Tree, you could keep track of the number of such operations and then just rebuild the whole tree after some threshold. I am curious if there are better approaches - let me know what you find!

[@ChrisOffner]

Fantastic explanation and visualisation, thank you so much! :)

[@stablesort]

Thanks for leaving a compliment!

[@卡机不]

Wow ！new episode updated ， i already cannot wait to learn it！thank you so much .

[@stablesort]

=) I hope you liked it!

[@dainel1490]

Thank you, I think it solved my problems with making kd-tree and searching it.

[@omnamahshivaya2054]

Your code saved me.

[@stablesort]

Good to hear it!

[@br3nto]

How does this compare to quad-trees? I’ve always wondered why they chose 4 partitions instead of 2. KD-trees seem the closest to this idea, but still a bit different.

[@StopHackingMe-mm3bk]

Thanks for this video. Could we adapt the algorithm to not get only the closest point but rather all points under a certain distance ?

[@Fanaindel3]

+++

[@FlorinGN]

Really nice explanation, thank you!

[@yeetgod5063]

I love this channel please upload more

[@stablesort]

Thank you

[@KingGJT]

Great video! Thank you for making math visible :)

[@br3nto]

Nice vid and nice animation! Short and digestible😃

[@pietertjeboersma6586]

Thanks for your clear explanation!

[@stablesort]

Glad you liked it! Cheers!

[@mohammadyahya78]

Amazing tutorial. Why the point (2, 6) splits the space into up and bottom and not left and right as the root node (5, 4) did please?

[@oren2234]

so if this was a 3D tree we would have to check potentially all 4 quadrants the neighbour might be in ? and if i had a 10D tree I would have to check 2^9 quadrants ?

[@stablesort]

Good question. The tree nodes still have only two child nodes, even if you have 10 properties per node. Take a look at the source code - the distSquared(point0, point1) uses all properties (3, 10, whatever) but since there are only two child nodes, the plane is always split into just two. I hope this answers your question but let me know if I can clarify further.

[@hanesburger8470]

Thank you from UC Berkeley!

[@TranCao-w8r]

how come the point (13,3) is closer to (9,4) than (8,7)? and because of that we never traverse to the point (10,2), why does this happen?

[@wouttengrootenhuysen5137]

Thank you very much for making this video !

[@volodymyrhavrylov7993]

Nice and clear explanation, thanks!

[@stablesort]

Thanks for the compliment! Cheers!

[@pawankumarpandit1822]

thaks dear i cant believe that what a amazing way to explanation it is a kind of unblievable again thank you sir and a lot of love

[@vctorroferz]

just an amazing explanation! thanks so much!

[@sensiblerazor9666]

Can you make a video on R-Trees and Multi-Dimensional Indexes?

[@stablesort]

That's a great topic and it'd definitely fit with the current discussion of KD-Trees. Thanks for suggesting it - adding it to the list!

[@panoramibyneel]

Did you notice the corn cob in a plastic pot? Some parsley would have worked better. Great video btw

[@stablesort]

I'll try parsley in my next video =)

[@Nick-qd5my]

Great explaination. Took my prof 1h and not even half as clear

[@stablesort]

8-) Thanks!

[@АртемСиробаба]

Thank you for great explanation !

[@stablesort]

You are very welcome!

[@anshumansharma6758]

Amazing explanation!!!

[@stablesort]

Thanks for the compliment! Glad to hear that you enjoyed it!

[@jcasteld]

Hi. Your videos are great. Do you have any other new channel or web page to follow you? Thanks.

[@alexanderhess7742]

Great video. Especially due to explaining r'.

[@stablesort]

Thanks for the compliment! Yeah, the radius concept is the tricky part.

[@sensiblerazor9666]

Nice explanation. Thanks!

[@stablesort]

Cheers!

[@joshyatharva]

Awesome!❤️ Can you please make videos on B and B+ trees?

[@stablesort]

Thanks for the compliment and a great suggestion. I'll add B and B+ trees to the "to do" list =)

[@balu.92]

Excellent lesson! Thank you!

[@stablesort]

Thanks!

[@AbJadzera]

Great video, thank you for doing it!!

[@stablesort]

Thanks! I am glad to hear it!

[@vijaynegi310]

Great explanation !! thanks

[@maksymchernetskyy6404]

nextbranch or otherbranch can be null, then temp will be null, then we put null in the function that gives us the closest point, so we put null instead of the point. seems like a problem of this pseudocode to me. What do we do in this situation? Just output as best the non null one or we go to the other branch?

[@SingularityLabsAI]

0:44 if all coordinate shares same x-coordinate then it becomes easier as we only need to check at most 2 points.

[@HH-mf8qz]

Nice And good visualization with the radius r

[@heitorgomes9496]

Well done, great explanation!

[@stablesort]

Thanks for the compliment!

[@brunasouzadarochasantos9929]

Excellent! Thank you so much!!

[@klausdupont6335]

Great video! Thanks!

[@stablesort]

Cheers!

[@anshugangwar7344]

First of all Very nice explanation , Do you have any video or code reference on Designing and implementing a binary space partitioning (BSP) tree with functions for adding nodes, printing the nodes in descending order and searching for the spatially closest node (along the one dimension)?

[@brucewernick6542]

What about N_Nearest_Neighbors? The logic for Nearest_Neighbor only works for the first.

[@maximstepanenko]

Beautiful explanation. Thank you. )))

[@shivamverma-mt6kp]

Great video. Please post the code in c++ or complete pseudo code.

[@stablesort]

I do have the full source code in Java: bitbucket.org/StableSort/play/src/master/src/com/stablesort/kdtree/KDTree.java

[@shivamverma-mt6kp]

@@stablesort Data structures in java is another trouble for me. I do data structures in c++ Please give the pseudo code atleast.

[@stablesort]

​@@shivamverma-mt6kp OK, here is a quick rundown: so you have a tree node, with left and right pointers (I called it KDNode). The "value" in that node could be a vector/array of integers, or encapsulated in some other object that just has that array/vector. I went with the second option, calling it KDPoint. class KDNode { KDNode left KDNode right KDPoint point ... } class KDPoint { List props // this could just be an array of int ... } // this is your main class with the algorithm to find the nearest neighbor: class KDTree { // reference to the root is all we need KDNode root // main method, described in the video: private KDNode nearestNeighbor(KDNode root, KDPoint target, int depth) { if (root == null) return null; KDNode nextBranch = null; KDNode otherBranch = null; // compare the property appropriate for the current depth if (target.get(depth) < root.point.get(depth)) { nextBranch = root.left; otherBranch = root.right; } else { nextBranch = root.right; otherBranch = root.left; } // recurse down the branch that's best according to the current depth KDNode temp = nearestNeighbor(nextBranch, target, depth + 1); KDNode best = closest(temp, root, target); long radiusSquared = distSquared(target, best.point); /* * We may need to check the other side of the tree. If the other side is closer than the radius, * then we must recurse to the other side as well. 'dist' is either a horizontal or a vertical line * that goes to an imaginary line that is splitting the plane by the root point. */ long dist = target.get(depth) - root.point.get(depth); if (radiusSquared >= dist * dist) { temp = nearestNeighbor(otherBranch, target, depth + 1); best = closest(temp, best, target); } return best; } // just picks the better option between n0 and n1, but does not traverse anywhere else KDNode closest(KDNode n0, KDNode n1, KDPoint target) { if (n0 == null) return n1; if (n1 == null) return n0; long d1 = distSquared(n0.point, target); long d2 = distSquared(n1.point, target); if (d1 < d2) return n0; else return n1; } ... } I believe this should be very close to C++ code. I hope this helps!

[@少年追梦]

amazy，thinks~ expect the next

[@stablesort]

You are very welcome!

[@johnvif]

awesome video!

[@stablesort]

Thanks for the compliment!

[@karenaguilar2228]

que facilito de explicar. so good

[@gimmemoreborisbrejcha9794]

Well, great work.

[@stablesort]

Cheers!

[@franciscoornelas4488]

Great content!

[@ram845-l4k]

Great video 👍🏻 could you please upload the code for deleting a node from the tree?

[@stablesort]

Thanks for the compliment. Deleting a node is not trivial, since you would have to either re-index all of the children nodes recursively or come up with some other scheme. Here are a couple from the top of my head: -just mark the node as deleted but not actually remove it. Then rebuild the tree once there are too many of these fake-deleted nodes. -move one of the leaf nodes in places of the deleted node

[@pawtha2238]

thanks for explanation in video. Please dont add background music, its distracting and annoying.

[@avink6074]

excellent !

[@nchm2625]

hi, thank you! I just ask myself what i need to do if i want to find not only my nearest neighbour but for example 5 or 6 nearest neighbours. Thanks :)

[@stablesort]

Sure, that would be a natural extension to this problem. I think the most intuitive solution would be to use an additional max-heap into which you keep adding points. Restrict the size of the heap to K (5 or 6 in your example). Whenever you add a point to the heap and the size becomes greater than K, remove the top element. The top element will be the one with the greatest distance. So ultimately you'll end up amassing K points with the shortest distance.

[@nchm2625]

@@stablesort That would be a great addition to this video though :D thank you for that one, now i need to learn about heap maps

[@stablesort]

@@nchm2625 If you are coding in Java, take a look at PriorityQueue class - it's Java's heap implementation. It can do exactly what you are looking for.

[@nchm2625]

@@stablesort Do you know if there is any literature about this specific problem, because i can't find anything? I'm greatful for every idea!

[@stablesort]

@@nchm2625 Try searching for "k nearest neighbors using kdtree", such as: stackoverflow.com/questions/34688977/how-do-i-traverse-a-kdtree-to-find-k-nearest-neighbors

[@madhuvarun2790]

what if the data has more than 2 dimensions, let's say 3? in the first layer if the chosen dimension is x what will be the dimension chosen in the second layer and third?

[@stablesort]

Thanks for posting a question. KD-Tree sequentially goes through each of the dimensions and then loops back. For example, if there are 3 dimensions, then it'd go in this sequence: 1, 2, 3, 1, 2, 3, 1, 2, 3, ... Typically this is easily implemented using MOD operator and the depth of the tree. So as you traverse deeper and deeper into the tree, you pass the 'depth' counter along. Then for a K dimensional tree, you'd pick dimension depth % K. Take a look at the source code linked in description for a sample implementation. Hope this helps!

[@smitdumore1064]

Beautiful

[@vasilispolychronakis5812]

why do you have a corn in a flower pot???

[@bshsmdshj1938]

thank you!🤞🤞

[@letoiiatreides2466]

we just gonna ignore the corn in the flower pot?

[@stablesort]

:-p

[@twisted_cpp]

Is this Mlepnos? Jokes aside, nice explanation.

[@frederickhamilton7663]

10/10 :-)

[@tomgt428]

So cool

[@stablesort]

Cheers!

[@simonsheldon1710]

ty for video

[@benripka6977]

Awesome

[@billwang1456]

3:59 good

[@rafaelromeromunhoz9826]

thankss

[@stablesort]

cheers!

[@adityarajora7219]

how to search for second nearest neighbor?

[@Артем-х7п6с]

Have you found a solution? I need to find the 5 closest points, but I can't figure out how to do it

[@adityarajora7219]

@@Артем-х7п6с still not, One stupid method is like delete the first node that you have found from the tree and then go for first node again, it will be your second.

[@ai__76]

The shown code is incorrect!!!

[@hifam9522]

Kevin Durant tree lesss go

[@humanvegetable]

🫡

[@parthivreddy7989]

orz