Предварительный выбор вероятности для приближенного совпадения строк

Недавно мне было поручено разработать алгоритм проверки дубликатов записей клиентов в базе данных.
Структура БД довольно проста: десятки тысяч строк с полями, такими как FullName, Street, City, ZIP, Phone и т. Д.

Сначала немного истории:

Я провел несколько обширных исследований алгоритмов и решил, что каждое поле должно быть взвешено в определенном количестве.
с разными алгоритмами, так как не все работают одинаково хорошо при любых обстоятельствах.
Например, LastName имеет весовой коэффициент 0,50. Когда я оцениваю, я выбираю, какие алгоритмы использовать и как они влияют на окончательное решение:
Коэффициент 0,25: Яро Винклер
Фактор 0,60: сходство косинуса 2-грамм
Фактор 0,15: Дамерау, Левенштейн

Все работает хорошо, и с небольшой настройкой я обнаруживаю позитивы с небольшой ошибкой.
Все идет нормально. Однако, как вы можете себе представить, наличие времени выполнения O (n ^ 2) — или фактически E-формы от i = 0 до i = n — не очень эффективно при работе с десятками тысяч записей.
Излишне говорить, что агрессивная оптимизация, использование оптимизаций компилятора для скорости, многопоточности и т. Д. — это просто бандиты, поскольку реальная проблема заключается в сложности.

По сути, я ищу способ предварительной фильтрации потенциальных совпадений и провел три дня исследований по этому вопросу сейчас.
Я нашел некоторую ценную информацию о R-деревьях, R * -деревьях, KD-деревьях, евклидовых векторах, minhashing, et al.
Тем не менее, большая часть информации обо всем этом, в общем, довольно академична. Самый ценный ресурс, который я нашел, был в «Mining Massive Data Sets», глава 3.

Теперь к моему настоящему вопросу:

Я прочитал всю эту информацию, но я не уверен, как собрать все это вместе.

Я думал о какой-то индексации в древовидной или графической структуре данных, где я могу вставить строку и сказать: «Найдите мне все, у которых есть вероятность совпадения> 0,20».
Этот алгоритм должен быть очень быстрым. Затем, когда я получу список потенциальных (> 0,20) совпадений, я мог бы пойти и сравнить несколько элементов с моим «дорогим», но выборочным алгоритмом.
Это должно сократить время выполнения до очень разумного значения, я считаю.

Я пытался найти какой-то справочный код, чтобы делать то, что я хочу сделать выше, но, похоже, я не придумываю ничего, кроме научных статей.
Я нашел «simstring», которая фактически компилировалась, но, похоже, не очень хорошо соответствовала 7 тестовым записям.
Кто-нибудь может указать мне правильное направление? Наверняка кто-то уже сталкивался с этим раньше и нашел решение …

Заранее большое спасибо!

Постскриптум Я делаю это в C ++, но все образцы в C # / C / Java / PHP будут в порядке.