Избегайте O (n ^ 2) при сопоставлении лиц в базах данных - параллельное сопоставление лиц

Question

У меня есть миллионы записей «людей», - говорят клиенты для первого клиента и клиенты для второго клиента.Мы хотим сопоставить людей в клиенте один и клиенте два вместе - например, обнаружение, что «г-н Джоэл Спольски» находится в базе данных клиента один, и сопоставление его с «J Spolsky» в клиенте два, создавая совершенно новую запись в «основной базе данных».

Точный алгоритм сопоставления двух кандидатов не важен, важно то, что наиболее очевидным решением является сбор каждой записи в клиенте один и сравнение с каждой записью в клиенте два.
Это быстро становитсяогромная задача, особенно с клиентами три четыре пять и т. д.

У кого-нибудь есть какие-нибудь интересные подходы для повышения производительности?

Answer 1

Единственный способ избежать O (n ^ 2) (или O (n ^ m), если имеется более 2 клиентов), это отсортировать базы данных перед поиском.

Но для того, чтобы их можно было отсортировать, вам нужно придумать какое-то нормализованное поле, которое всегда будет точно соответствовать клиентам. (например, последнее слово в поле имени + почтовый индекс и все это вынуждено вводить нижний регистр)

Если вы можете сортировать базы данных, вы можете уменьшить свой алгоритм до O (n log n)

Answer 2

Самый очевидный способ - создать общий алгоритм сортировки для всех баз данных. Сортируйте базы данных по спискам, сравнивайте «верхние» элементы в каждом отсортированном списке, затем продолжайте отбрасывать «самый ранний» элемент, пока не найдете два соответствующих элемента. Запишите матч, отмените его и продолжайте.

Это работает очень хорошо, если у вас есть, скажем, два набора номеров ISBN книг для сравнения, чтобы найти дубликаты между двумя библиотеками, но не очень хорошо с именами людей, имена которых могут не совпадать (например, Дж. Смит против Джона Смита) , Вы можете несколько улучшить ситуацию, используя своего рода схему KWIC, где вы делаете несколько записей в своем отсортированном списке для каждой записи в БД - например, одна запись для имени, одна запись для адреса, одна запись для номера социального страхования - независимо от того, какие критерии вы используете может решить, чтобы соответствовать. Также может быть полезен перевод имен в формате Soundex.

Answer 3

это сильно зависит от базы данных.Обычно «пересечение» является самым быстрым.

Теперь у вас есть небольшая разница между двумя именами в вашей базе данных: «Mr Joel Spolsky» и «J Spolsky»

Это означает предварительную обработку таблицы,чтобы убедиться, что имя совпадает, и, возможно, напишите свой собственный «фонетический» индекс.это кажется неуместным, но если у вас есть совпадение столбца «имя» и «имя», а не «префикс» столбца, что вы делаете?(Мистер и миссис Алекс Джонс).

До того, как вы это узнаете, у вас есть механизм правил, механизм принятия решений и интерфейс для всех «ручных» случаев (которые не являются автоматическими слияниями или определенными не совпадают) и 3 ученика.объединение (или пометка как «не имеющее имя») миллионов адресов на полный рабочий день.

Итак, прежде чем попасть туда, определите, что вы хотите объединить точно , тогда алгоритм можно легко выбрать

Answer 4

Алгоритм сопоставления важен .Если вы ничего не знаете об алгоритме сопоставления, вам нужно сравнить каждый из них в другой клиентской базе данных, и вы получите O (N ^ 2).