Как правильно организовать базу?

Добрый день. Тут теперь технологии поиска обсуждаются?

Вот натолкнуся на интересную статью:

http://www.sc2001.org/papers/pap.pap338.pdf

"Compressing Inverted Files in Scalable Information Systems by Binary Decision Diagram Encoding"

Как я понял, авторы предлагают использовать "Binary Decision Diagrams" вместо инвертированных индексов. При этом утверждают что и размер индекса меньше, и скорость поиска выше (для булевых запросов).

По теме в инете очень мало инфы, статья написана в 1994 году. Чувствую что революции она не сделала, значит есть в этом подходе какие-то проблемы.

Не подскажете ли в чем они состоят? или куда копать чтоб самому разобраться?

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

Тема эта не очень модная - считается, что на современных машинах примитивное сжатие листов - дельта+байт-ориентированное кодирование, дает приемлемый результат в 99% случаев. Более сложные алгоритмы в большинстве случаев дают только проценты улучшения сжатия, а быстродействие начинает падать, да и не заплатит никто за эти сложности - мегабайты на hdd копейки стоят :).

ага, точно. я мерил байтовое кодирование дельт скорость распаковки 40метров в секунду, битовое - выигрыш в размере 5-10%, а скорость распаковка 2-4 метра в секунду. почуствуйте разницу.

А как обстоят дела с поиском в длинных постингах (т.н. Zig-Zag joins)? Можно ли считать "Self-Indexed Inverted Files" от Зобеля приемлимым на данный момент решением?

Или действовать как предлагают в "Building a Distributed Full-Text Index for the Web" - словарь в B-tree c mixed-list в базе данных (ИМХО как-то сомнительно что это эффективно).

Или это тоже уже не модная тема и все давно устарело? :)

Может чего присоветуете....

(В общем-то решая эту проблему я и наткнулся на эти BDB - Binary Decision Diagram)

Спасибо

Эти вещи не противоречат друг-другу. Я люблю использовать Б+ деревья, где для длинных пост-листов ограничения на размеры слота естественно образуют эти skip points Зобела, а поверх можно делать Zig-Zag joins. В статье "Building distr..." их проблема в Berkley-DB там не очень удачно реализованы деревья в случае слотов переменной длины, чем отчасти и обусловлены результаты.

http://www.megawap.ru/~wap/dev/approximate_search.htm

http://cito-web.yspu.yar.ru/link1/metod/theory/node35.html

Для начала вот это.

Приятно, конечно, стать объектом цитирования, но первая ссылочка ИМХО немножко не подходит под данную тему.

По поводу зиг-загнутых джойнов и само-инвертированные файлов. Несомненно для достаточно длинных (избирательных) запросов разрезание инвертированных списков на куски ускоряет процесс пересечения списков и довольно прилично экономит память. Под достаточно длинным я понимаю такой, у которого после выборки и пересечения N ключевых слов образуется небольшое количество диапазонов номеров документов, в которых могут быть результаты. Тогда, в процессе пересечения с последующими инвертированными списками (с номерами N+1, N+2, ...) не нужно будет вытаскивать списки целиком, а только кусками. В принципе, N может равняться и 1, если в запросе есть достаточно низкочастотное слово.

Проблема в том, что это экономия "в среднем" в худшем случае, всегда можно подобрать запросов из частотных слов, когда эта технология окажется бесполезной и на запросе из 5-10 слов. Что делать с такими тяжелыми и не очень запросами - большой вопрос, но в целом техника эшелонирования (pruning) должна помогать.

Еще одна модная тенденция заключается в том, чтобы разрезать индекс на примерно одинаковые куски, каждый из которых кешируется на 80-90%. Сейчас это стало недорого, благо 4гига памяти воткнуть в машину - не проблема. А в 4 гига памяти можно лего уложить индекс

8 гигов чистого текста, ну или примерно 2-4 млн средневебовских документов. А когда индекс хорошо закеширован, то зюгзаги работают очень хорошо, не сравнить со случаем, когда это все с диска загружается, потому как чтение с диска с небольшими, скажем по нескольку сотен байт пропусками фактически не быстрее, а иногда даже медленнее, чтения всего файла последовательно.