Как lucene вычисляет пересечение документов так быстро?

Что такое внутренние хранилища и поиск, которые позволяют это? Как в nitty gritties?

Например, у меня есть миллион документов, согласованных термином и миллионом других, сопоставляемых вторым термином запроса И. Как lucene делает пересечение так быстро, что дает мне верхнюю часть?

Сохраняет ли документ документ в порядке возрастания ID документа для каждого термина? И тогда, когда нужно заключить документы с двумя терминами, он ищет первые общие k-документы в обоих наборах, повторяя их как поэтапно, за один проход.

Или он использует простой неупорядоченный хеш-набор из массива больших документов, чтобы найти общие документы?

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

Будут оценены любые статьи, которые могут указывать на слияние элементов массива документа.

Изменить: Спасибо за информацию, ребята. Теперь это имеет смысл. Пропустить списки делают магию. Я буду копать в него больше, чтобы получить четкое понимание.

Ответы

Ответ 1

  • Индексы содержат отсортированные документы. когда вы запрашиваете оператор и оператор (term1 AND term2), он использует два итератора, поэтому, когда вы знаете, что первый term1 начинается с docN, вы можете пропустить весь документ для term2 до docN. Таким образом, существует не только итератор со следующим методом, но и очень эффективный метод skipTo. Он реализуется с индексом Пропустить список (http://en.wikipedia.org/wiki/Skip_list). Поэтому, используя метод next и skipTo, мы очень быстро переходим к большим фрагментам, а поскольку данные разрежены (например, они не будут работать для обычной базы данных), это очень эффективно.
  • Другое дело, что lucene удерживает только N лучших, поэтому он намного быстрее, чем сортировать все документы. Если вы запросите 10 лучших, это будет вдвое быстрее, чем если вы запросите 20 лучших документов.

Ответ 2

Lucene будет пересекать отсортированные идентификаторы документов или использовать окна битов в зависимости от ситуации. См. Комментарии вверху BooleanScorer.