Оптимизация запросов — логический поиск конъюнктивных запросов

Я прохожу курс информационного поиска, где мы начали с «логического поиска».

Я столкнулся со следующим вопросом (взято из Стэнфордской книги по информационному поиску):

Для конъюнктивного запроса гарантируется ли оптимальная обработка списков сообщений в порядке их размера? Объясните почему/почему нет.

Дается следующее объяснение:

Порядок не гарантируется оптимальным. Рассмотрим три термина с размерами списка постов s1=100, s2=105 и s3=110. Предположим, что пересечение s1 и s2 имеет длину 100, а пересечение s1 и s3 — длину 0. Упорядочивание s1, s2, s3 требует 100+105+100+110=315 шагов по спискам проводок. Порядок s1, s3, s2 требует 100+110+0+0=210 шагов по спискам проводок.

Может ли кто-нибудь объяснить вышеизложенное?

Например: В "100+105+100+110"; что означает 100? Это размер s1 или пересечение между s1 и s2? (105 и 110 довольно очевидны).


query-optimization boolean-logic boolean-operations theory
person northerner    schedule 10.02.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Согласно вопросу, вы должны обрабатывать списки сообщений в возрастающем порядке (с размером). Учитывая s1 = 100,s2 = 105,< strong>s3 = 110. Итак, сначала нужно обработать s1 и s2. Допустим, вы получили r1 = s1. И s2, то вы должны обработать r1 и s3. введите здесь описание изображения

По алгоритму можно оценить расход.

Поскольку s1 AND s2 = r1, а r1 имеет длину 100. Теперь потребление: O(s1+s2) = 100 + 105 = 205, затем вы обрабатываете r1 с s3, потребление составляет O(r1+s3) = 100 + 110 = 210, значит, весь расход 205 + 210 = 415.

Но мы уже знаем, что s1 AND s3 = 0, поэтому мы должны обработать s1 и s3 сначала с потреблением O(s1+s3) = 100+110 = 210, назовем его r2. Наконец, обработайте r2 и s2, O(r2+s2) = 0 (поскольку r2 имеет длину 0). Таким образом, общее потребление равно 210 + 0 = 210, что меньше 415.

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

person Peter Guan    schedule 14.05.2016