Вероятно, одно из самых горячих сообщений в блоге, которые я прочитал год или около того назад: Levenstein Automata . Посмотрите на эту статью. Он предоставляет не только описание алгоритма, но и код для подражания. Технически, это не kd-дерево, но оно весьма связано с алгоритмами сопоставления строк и словарного исправления, с которыми можно столкнуться / использовать в реальном мире.
У него также есть еще одно сообщение в блоге о BK-деревьях , которые гораздо лучше справляются с нечетким соответствием строк и поисков строк, где есть неправильное написание. Вот еще один ресурс, содержащий исходный код для BK-дерева (в этом я не могу проверить точность или правильную реализацию.)