Damn Cool Algorithms: BK-Trees
blog.notdot.net
Damn Cool Algorithms: BK-Trees
1–10 of 11 posts
Re: Damn Cool Algorithms: BK-Trees
#2Very cool. Has anyone here used BK-Trees in their work?
Re: Damn Cool Algorithms: BK-Trees
#3I don't see why this would be much better than simply doing fuzzy match on a trie.
Re: Damn Cool Algorithms: BK-Trees
#4I don't see why this would be much better than simply doing fuzzy match on a trie.
How do you do a fuzzy match? Are there any sites out there that deal with all the text matching algorithms? I need to do this for a project.
Re: Damn Cool Algorithms: BK-Trees
#5Needs more code.
Re: Damn Cool Algorithms: BK-Trees
#6I couldn't understand what this means -- Say we take an arbitary string, test and compare it to query. Call the resultant distance d. Because we know the triangle inequality holds, all our results must have at most distance d+n and at least distance d-n from test.
Can anyone please explain me in more simpler terms.
Re: Damn Cool Algorithms: BK-Trees
#7I couldn't understand what this means -- Say we take an arbitary string, test and compare it to query. Call the resultant distance d. Because we know the triangle inequality holds, all our results must have at most distance d+n and at least distance d-n from test. Can anyone please explain me in more simpler terms.
It's easiser to understand by using 2D geometry. Pick one point on a paper and call it query, the input, and draw a circle of radius n around that point. Your goal is to find the points in the dataset which are inside the circle. Let's call those points answers.
Pick an arbitrary point (in the dataset) and call it test. The distance between test and query is d. Now, you can see the distance between test and the furthest and closest points in answers are d+n and d-n, respectively (assuming d > n).
Since the dataset is organized by distance, we can quickly narrow the range of search.
Re: Damn Cool Algorithms: BK-Trees
#8I don't see why this would be much better than simply doing fuzzy match on a trie.
How do you do a fuzzy match? Are there any sites out there that deal with all the text matching algorithms? I need to do this for a project.
No websites, probably, but lots of papers. A good start might be http://courses.csail.mit.edu/6.851/spring07/lec.html (lectures 8 and 9 or so).
Re: Damn Cool Algorithms: BK-Trees
#9I couldn't understand what this means -- Say we take an arbitary string, test and compare it to query. Call the resultant distance d. Because we know the triangle inequality holds, all our results must have at most distance d+n and at least distance d-n from test. Can anyone please explain me in more simpler terms.
It's easiser to understand by using 2D geometry. Pick one point on a paper and call it query , the input, and draw a circle of radius n around that point. Your goal is to find the points in the dataset which are inside the circle. Let's call those points answers . Pick an arbitrary point (in the dataset) and call it test . The distance between test and query is d . Now, you can see the distance between test and the f…
thanks dude, for clearing it up. I don't know why I always get confused on easy things like this..
Re: Damn Cool Algorithms: BK-Trees
#10Earlier quoted context omitted.
How do you do a fuzzy match? Are there any sites out there that deal with all the text matching algorithms? I need to do this for a project.
No websites, probably, but lots of papers. A good start might be http://courses.csail.mit.edu/6.851/spring07/lec.html (lectures 8 and 9 or so).
Thanks.