Как вариант. Можно привести сначала строки к какому-то "нормализованному виду". Например, удалить всё кроме букв, удалить места с наиболее вероятными ошибками (буквы а, о), заменить всю кириллицу на латиницу и т.п. и затем положить это всё в в словарь, где каждому такому "хэшу" будет соответствовать 5-10 похожих наименований. При добавлении новой записи сначала вычислять "хэш", затем по соответствующим ему 5-10-15ти записям пройтись нормальной функцией поиска соответствия. Идея в том, чтобы не шерстить все 70к каждый раз, более 90% из них очевидно даже близко не похожи. Собственно нужно просто подобрать способ как отфильтровать эти 90+% заранее.
