Я проектирую облачную архитектуру на AWS для системы, обрабатывающей большое количество объектов. Я надеюсь, что это правильный StackExchange для этого вопроса (мне это не показалось подходящим - не стесняйтесь переносить вопрос).
Описание проблемы
У меня большое количество (допустим, п = 1 000 000 для этого сценария) сущностей в базе данных (объекты, доступные по их ключам - в основном база данных noSQL). У меня есть алгоритм, который может брать два объекта и выдавать значение, указывающее на их сходство (допустим, вычисление занимает около 10 мс).
Система должна иметь возможность сравнивать произвольную сущность со ВСЕМИ сущностями в моей БД, а также выявлять все дубликаты в моей БД (что означает сравнение каждой сущности с другой сущностью!).
дизайн
Я изложил это на бумаге и сделал некоторые базовые оценки (с разумным количеством рабочих, использующих несколько потоков каждый) и выяснил, что на выполнение идентификации дублирования уходит слишком много времени - это достаточно хорошо для сравнения «один против всех», но пытается выполнить 1000000 ^ 2 операций - это слишком много.
Я думал об использовании Hadoop с MapReduce, но мне кажется, что мне придется запускать новое задание для каждого сравнения «одно против другого» (а выполнение миллиона заданий звучит не очень быстро).
Поэтому я был бы очень рад любым предложениям, как улучшить мой дизайн и преодолеть эти подводные камни. Более того, задача (каждое сравнение по сравнению с каждым) выполнима даже без необходимости запуска сотен мощных экземпляров (цена также является ограничением).
Если вы ищете «дубликаты» и ваша метрика является евклидовой, то вам, вероятно, не нужно знать расстояния между далекими объектами. Поиск в Google чего-то вроде "эффективных знаний", скорее всего, поможет вам встать на правильный путь.
Интуитивная аналогия: если вы ищете соседей в пределах 50 км от кого-то в Греции, не тратьте много времени на расчет расстояний до всех людей в США. Эти расстояния никогда не будут важны для поиска соседей.