The SISAP metric spaces library comes with an implementation: http://sisap.org/Metric_Space_Library.html http://sisap.org/Metric_Space_Library.html You can als

The SISAP metric spaces library comes with an implementation: http://sisap.org/Metric_Space_Library.html 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.