News for hackers. Stuff that matters.
Re:Damn Cool Algorithms, Part 1: BK-Trees by grandpa on Monday December 05, 2011 @08:40AM (#3314504)
Re:Damn Cool Algorithms, Part 1: BK-Trees by rhnet on Monday December 05, 2011 @04:11PM (#3316503)
I couldn't get the link to the Python version to work, but I wrote my own a while back.

https://github.com/sholiday/pyBKTree

Re:Damn Cool Algorithms, Part 1: BK-Trees by thesystemis on Monday December 05, 2011 @09:50AM (#3314763)
Re:Damn Cool Algorithms, Part 1: BK-Trees by ahupp on Monday December 05, 2011 @05:33PM (#3316847)
Here's where the python one above (as well as a different haskell version) lives now: https://github.com/ahupp/bktree
Re:Damn Cool Algorithms, Part 1: BK-Trees by zszugyi on Monday December 05, 2011 @02:03PM (#3315921)
IMHO the explanation on the Lisp implementation page is much clearer then the article.
Re:Damn Cool Algorithms, Part 1: BK-Trees by dman on Monday December 05, 2011 @03:43PM (#3316382)
If you hang out in the lisp community you will find this to be a recurring theme - the quality of the community and the textbooks makes lisp a great learning language even if you never write a line of lisp code in production. fwiw as a current outsider the haskell community gives me the same feeling that the discourse in the community is of pretty high quality.
Re:Damn Cool Algorithms, Part 1: BK-Trees by omaranto on Monday December 05, 2011 @06:42PM (#3317067)
What an odd thing to say! The Lisp implementation page has no explanation that I could find of either how to build the tree or how to search it. Or did you mean you found the source code to be a clearer explanation?

Edit: The lisp page does have a nice picture of a tree. Did you mean that looking at that picture you could figure out both the algorithm for building the tree and for querying it and the proof that these are correct faster than by reading Nick's blog post?

Re:Damn Cool Algorithms, Part 1: BK-Trees by zszugyi on Tuesday December 06, 2011 @01:04AM (#3318188)
I meant that the picture explains the tree's structure much clearer than the blog post, which is probably not surprising. Didn't really look at how to build or query the tree.
Re:Damn Cool Algorithms, Part 1: BK-Trees by wgd on Monday December 05, 2011 @06:21PM (#3317010)
This seems similar to the VP-Tree, which there was a post about a few days ago, except that VP-Trees use binary partitioning because they're measuring similarity in a continuous space, while these ones use discrete buckets because similarity is measured discretely.
Re:Damn Cool Algorithms, Part 1: BK-Trees by gujk on Monday December 05, 2011 @11:34PM (#3317903)
The VP article linked to this one as background material. That is where OP found this article to repost for karma.
Re:Damn Cool Algorithms, Part 1: BK-Trees by leeoniya on Monday December 05, 2011 @10:51AM (#3315050)
i especially like the part where it says. "The only copy of this online seems to be in the ACM archive, which is subscription only."
Re:Damn Cool Algorithms, Part 1: BK-Trees by kjhughes on Monday December 05, 2011 @12:57PM (#3315600)
To clarify, Nick Johnson is referring to the original paper on the topic ("Some approaches to best match file searching" by Burkhard and Keller in 1973). It's a common frustration that ACM archives are not freely available to the public.

In the comments, "Sarah" notes that the paper can be found here:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.160...

BTW, Nick's Blog often has gems and is well worth a regular read.

Re:Damn Cool Algorithms, Part 1: BK-Trees by arnoldoMuller on Monday December 05, 2011 @11:37PM (#3317917)
The SISAP metric spaces library comes with an implementation: http://sisap.org/Metric_Space_Library.html You can also compare BK-trees with other methods and you may encounter that their performance is not so great, specially for high dimensional spaces.