Дедупликация с нечетким соответствием менее чем за экспоненциальное время?

У меня есть большая база данных (потенциально в миллионах записей) с относительно короткими строками текста (в порядке адреса, имен и т. Д.).

Я ищу стратегию для удаления неточных дубликатов, и нечеткое сопоставление, кажется, является методом выбора. Моя проблема: многие статьи и вопросы SO касаются сопоставления одной строки со всеми записями в базе данных. Я хочу выполнить дедупликацию всей базы данных сразу.

Первый будет проблемой линейного времени (сравнение значения с миллионом других значений, каждый раз вычисляя некоторую меру подобия). Последнее представляет собой экспоненциальную проблему времени (сравните значения каждой записи со значением каждой другой записи; для миллиона записей это примерно 5 x 10 ^ 11 вычислений по сравнению с 1 000 000 вычислений для первого варианта).

Мне интересно, есть ли там это другой подход, чем упомянутый мною метод "грубой силы". Я думал о том, чтобы, возможно, сгенерировать строку для сравнения значения каждой записи, а затем сгруппировать строки, которые имеют примерно равные меры сходства, а затем запустить метод грубой силы через эти группы. Я бы не добился линейного времени, но это может помочь. Кроме того, если я обдумываю это правильно, это может пропустить потенциальное нечеткое совпадение между строками A и B, потому что их сходство со строкой C (сгенерированная контрольная строка) очень отличается, несмотря на то, что они очень похожи друг на друга.

Есть идеи?

PS Я понимаю, что, возможно, использовал неправильные термины для определения временной сложности - это концепция, которая у меня есть базовое представление, но недостаточно хорошо, чтобы я мог сразу же отбросить алгоритм в нужную категорию. Если я неправильно использовал термины, я приветствую исправления, но, надеюсь, я хотя бы понял свою точку зрения.

Править

Некоторые комментаторы спрашивали, учитывая нечеткие совпадения между записями, какова моя стратегия, чтобы выбрать, какие из них удалить ( т.е. данные «foo», «boo» и «coo», которые будут помечены как дубликаты и удалены). Замечу, что здесь я не ищу автоматического удаления. Идея состоит в том, чтобы пометить потенциальные дубликаты в базе данных из более чем 60 миллионов записей для проверки и оценки людьми. Ничего страшного, если есть несколько ложных срабатываний, если это приблизительно предсказуемая / постоянная сумма. Мне просто нужно понять, насколько распространены дубликаты. Но если для выполнения нечеткого сопоставления требуется месяц, это вообще не вариант.