Каков алгоритм поиска в индексе нескольких значений?

Question

На самом деле это настоящая проблема, над которой я работаю, но для простоты давайте представим, что я Google.

Скажем, пользователь ищет "наноразмерный контейнер". Там не очень много страниц с обоими словами ... только около 3к. Но есть ~ 2 миллиона страниц с «наноразмером» и ~ 4 миллиона с «tupperware». Тем не менее, Google находит 3k для меня за 0,3 секунды.

Как это сделать?

Единственный известный мне алгоритм - это получить документы для «наноразмера», получить документы для «tupperware», а затем выполнить слияние списка. Но это O (N + M) или O (5 000 000), что кажется немного медленным. Особенно, если я запускаю его на настольном компьютере вместо сверхбыстрого кластера.

Так это на самом деле то, что делает Google, и их скорость объясняется главным образом тем, что они выполняют эти дорогостоящие вычисления в своем массивном распределенном кластере?

Или есть лучший алгоритм, о котором я не знаю? Википедия и Google ничего мне не показывают.

Edit:

Поскольку люди, кажется, сосредоточены на аспекте Google моего вопроса, я думаю, что я перефразирую его в реальных терминах.

У меня есть несколько очень больших (миллионы элементов) индексов, реализованных в виде пар ключ / значение. Ключи - простые слова, значения - наборы документов. Распространенным вариантом использования является пересечение результатов нескольких поисков по разным индексам: основной проблемой является пересечение наборов документов.

Я могу заново реализовать свои индексы, как захочу - на данный момент это в основном академический проект.

Answer 1

Как вы описываете, у вас уже есть инвертированный индекс , со списком проводок для каждого термина (списком документов). Я не знаю лучшего решения, чем объединение, объединяющее списки рассылки для каждого термина, и, насколько мне известно, это то, что делают решения для полнотекстовой индексации, такие как Lucene. Здесь можно сделать несколько очевидных оптимизаций:

1. Если вы можете хранить свой набор данных в памяти, даже распределенной по многим машинам, вы можете объединить объединение наборы результатов действительно очень быстро, по сравнению с тем, что потребовалось бы для поиска диска.
2. «Наивный» алгоритм объединения слиянием продвигает один указатель на одну позицию в каждом несоответствии, но если ваши списки публикаций сами проиндексированы, вы можете сделать это намного лучше, взяв максимум отдельных текущих значений и ища во всех остальных списках проводки первое значение больше или равно этому ключу - возможно, пропуская в процессе миллионы ненужных результатов. Это называется объединение зигзагом .

Answer 2

То, что вы описываете, называется н-грамм .

Google использует алгоритм под названием PageRank для поиска и сортировки результатов, который реализован с использованием MapReduce .

Все эти темы подробно обсуждались в прошлом в Stackoverflow. Их должно быть довольно легко найти.

Это, вероятно, не поможет вам в целом, поскольку у вас, вероятно, нет огромной распределенной системы для запуска MapReduce, но, поскольку вы на самом деле не дали нам никакой информации о том, что вы пытаетесь index , трудно предложить что-то подходящее для вашей проблемы.