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

Question

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

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

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

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

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

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

Edit:

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

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

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

Answer 1

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

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

Answer 2

То, что вы описываете, называется n-grams.

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

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

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