Порядок оценки обратного индекса

Question

Я где-то читал, что, когда у вас есть инвертированный индекс (например, у вас есть отсортированный список страниц брутуса, отсортированный список страниц для цезаря и отсортированный список страниц для кальпурнии), когда вы делаете цезарь Иbrutus AND calpurnia, если количество страниц для calpurnia и brutus меньше, чем количество страниц для caesar, то вам следует выполнить caesar AND (brutus и calpurnia), то есть сначала вы должны оценить последнее AND.В общем, когда у вас есть серия AND, вы всегда сначала оцениваете пару с наименьшим количеством страниц.В чем причина этого?Почему это эффективно?

Answer 1

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

Чтобы увидеть эффект от этого, предположим запрос caesar AND brutus и предположим, что есть страницы _Цезарь для caesar и _brutus страницы для brutus ( то есть occ _X обозначает длину списка страниц для термина X). Теперь предположим, для примера, что в контенте встречается * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *, т.е. * 10 * * *, то есть caesar * встречается в содержании чаще, чем brutus.

.

Затем вы должны повторить по всем страницам для brutus сначала и найти для каждой из них в списке страниц для caesar. Если в действительности списки можно искать в логарифмическом времени, это означает, что вам нужно

occ _brutus * log (occ _caesar )

вычислительные шаги для идентификации всех страниц, которые содержат оба термина.

Если вы сделали это в обратном порядке (т. Е. Итерация по списку caesar и поиск каждой из его страниц в списке brutus), меньшее число окажется в логарифме, и большее число станет фактором, поэтому общее время, затрачиваемое на оценку, будет больше.

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

Answer 2

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

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

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

Предположим, что мы заинтересованы в оценке запроса ключевого слова a b c, где a, b и c - слова в документах. Также предположим, что количество соответствующих документов следующее:

a --> 20
b --> 100
c --> 1000
a+b --> 10
a+c --> 15
b+c --> 50
a+b+c --> 5

Обратите внимание, что (a JOIN b) имеет размер 10, а (b JOIN c) имеет размер 50. Таким образом, первое требует 10 доступа к индексу на c, а второе требует 50 доступа к индексу на a. Но при использовании индекса на основе хеша или на основе дерева такой доступ к индексу не сильно отличается по стоимости и обычно осуществляется за один ввод / вывод.