Эти вещи не противоречат друг-другу. Я люблю использовать Б+ деревья, где для длинных пост-листов ограничения на размеры слота естественно образуют эти skip points Зобела, а поверх можно делать Zig-Zag joins. В статье "Building distr..." их проблема в Berkley-DB там не очень удачно реализованы деревья в случае слотов переменной длины, чем отчасти и обусловлены результаты.
В данном подходе нет проблем - это один из алгоритмов сжатия пост-листов из сотни предложенных. Основные его недостатки - подходит только для пост-листов без положений, старый - сейчас есть более эффективные подходы.
Тема эта не очень модная - считается, что на современных машинах примитивное сжатие листов - дельта+байт-ориентированное кодирование, дает приемлемый результат в 99% случаев. Более сложные алгоритмы в большинстве случаев дают только проценты улучшения сжатия, а быстродействие начинает падать, да и не заплатит никто за эти сложности - мегабайты на hdd копейки стоят :).
Не буду вдаватьс в подробности, чтобы никому не было обидно:
1. Я согласен с Ильей, что на практике (особенно на относительно небольших коллекциях) разница в 100 раз крайне редко возникает, на самом деле может разы-порядки.
2. Я согласен с Леонидом, что при относительно большой коллекции и однословному запросу легко можно разогнать инвертированный файл в 100 раз по сравнению с не очень удачной реализацией поверх СУБД.
Насчет плотности Б-дерева - немного подкрутив алгоритм вставки/удаления можно держать ту плотность, какую хочешь, хоть все время 100%, только обновление будет тогда достаточно дорогое.
Пошел высоконаучный спор :). Леонид, ты немного не понял как они строят индекс, 50% для Б-дерева это теоретическая худшая плотность, реально всегда намного лучше.
Но в общем, я согласен (хотя Илья на самом деле этот тезис не опровергал), что использовать SQL общего назначения для организации инв. файла - все равно что пытаться минивен доделать до болида формулы 1. С другой стороны, я твердо уверен, что инвертированный индекс поверх B-дерева при правильной организации будет не менее эффективен, чем при "классическом" построении.
Да, это тексты документа. Это "хорошие" pdfы
Это, конечно, шутка. Но что надо знать о стандарте кроме спецификации, а она есть? Просто он разрабатывается на 10 лет позже PDF, там все предусмотрено для поддержки языков не на латинском алфавите и т.к. это XML, то индексатор для него делается минут за 20, в этом смысле, действительно, счастье.
Не знаю как у Яндекса, но я сам писал однажды индексатор PDF и могу сказать, что для русских документов, подготовленных стандартным дистиллятором в 90%, случаев извлечь текст невозможно. Точнее единственный способ - распознать его как графику, как делает FineReader у которого есть такой конвертор, но никто из поисковиков этого явно не делает. Я проверял как работает родной Adobe IFilter для MS IS - та же картина.
Почему это происходит рассказывать долго, но кратко потому, что это почти графический формат.
Теоретически в PDF можно заложить любые поля типа автор, ключевые слова и т.д, но опять же в реальных PDF этого не встречается.
Короче, ждем когда Metro убьет PDF и разработчикам документооборотов наступит счастье :).
Все замечательно, НО:
1. Ваш пример плохой работы "фразового поиск" показывает, что у Вас плохо реализована нормализация документов по длине. Это действительно проблема, но не смертельная и она не обязательно есть во всех других реализациях. Другого обоснования (хотя оно теоретически есть и известно каждому специалисту по IR) почему по короткой фразе трудно хорошо искать не приводится. Это почему?
2. Хорошо известно несколько алгоритмов нахождения "похожих" документов, хорошо бы на них сослаться и дать какое-то сравнение, один пример гугла как-то не убеждает, тем более что он достаточно искусственный. Я за 5 мин. могу для вас обратный соорудить :). Можете кратко сравнить?
Да, я это читал, когда-то давным-давно, но забыл. Им, конечно, виднее :). С точки зрения частичной пересмотройки, поиска фраз (о чем мы говорили), масштабируемости и устойчивости к потерям узлов кластера это решение не очень.
Такая проблема есть в любой динамической индексной структуре. Простое и, обычно, хорошее решение предложил в 60-х г-н Bayer для листов Б-дерева.
Честно не слышал о таком решении. Во всех известных мне вариантах кластерного решения информация об одном документе помещалась на одном узле. Это естественно вытекает из более простой реализации индексации и поиска.
