Кстати, Максим недавно как-раз анонсировал, что может несколько десятков млн документов индексировать на одной машине. Видимо, это как раз с помощью прунинга. Но, с прунингом надо поосторожнее :-)
Здесь про trie http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic7/
и вооще погулить лучше, наверное, в гугль-скаляр
Максим, наверное, рассказывал про pruning. Да, действительно, неплохая штука для больших баз данных, только эвристики отбора значимых и незначимых документов должны быть "хорошие". Причем я сразу не готов сказать, какие хорошие, а какие плохие, да и опыта соответствующего нет.
Насчет хранения словаря: по-моему это ИМХО практически без разницы, для коллекции в несколько десятков миллионов документов словарь не будет больше 5-10 млн словоформ (это по опыту). В память влезет. Для слов, про которые известно, как они склоняются и спрягаются, лучше и дуобнее хранить словарь ИМХО в виде trie-дерева.
Ну, в общем-то, Eugen, Вы все сами написали. ИФ индекс получается из прямого фактически сортировкой (и последующим сжатием). Сортировка файла, который не влезает в память целиком можно делать так: разбить на N кусков, каждый отсортировать в памяти, записать на диск. Потом нужно сделать то, что кажется называется сортировкой с многопутевым слиянием. То есть идем по всем файлам одновременно, храним в памяти большой отсортированный буфер, как только он заполняется сбрасываем его на диск. Из какого куска считывать очередную запись решаем по правилу: если в текущем буфере сама "маленькая" запись считалась из куска i, то из него и считываем. Вставляем в отсортированный буфер, чтобы он оставался отсортированным.
По поводу правильного кодирования инв. списков с координатами. Все примерно тоже самое, что и без координат. Ситуация, конечно несколько осложняется тем, что если номера документов монотонно растут, то номера позиций растут только для записей из дного документа, пример
(0, 1) (0, 4) (0, 7) (1, 24) (1, 25) (3, 48) (4, 1)
в скобках первое число номер документа, второе - позиция. Можно, например, просто хранить две последовательные дельты: одну для документа, другую для позиции. Разумеется, если начинается новая "серия" позиций внутри документа, то первое значение - абсолютное, не относительное.
Только, надо иметь в виду, что битовые схемы кодирования не очень быстрые. Байтовые и словные и полусловные могут быть гораздо быстрее. С моей реализацией дельты и байтового кодирования разница чуть не в 10 раз была.
У зобеля есть много интересных и полезных статей на тему ИФ
(гляньте на его страничке)
, например,
"Efficient single-pass index construction for text databases"
"Compression of Inverted Indexes For Fast Query Evaluation" (это на тему byte-aligned методов)
читал и плакаль... терпеливый товарищ оказался :-) правда, Родина, щедро поила и кормила, поэтому у товарища взамен осталась масса впечатлений :-)
Про мульти-моду был тут недавно флейм на тему хорошего представления данных в базе. Просто если все разложить "по-правильному" в реляционные таблицы, то общая эффективность будет невелика. Наибольшая скорость должна быть в cache-mode и ее аналогах.
Подождите, а записей в базе, это именно в blob-mode? А 56000 тысяч HTML-страниц? Вы в блоб-моде индексируете? По поводу перехода на оракл: есть подозрение, что все только замедлится. По поводу распределенной индексации: вроде что-то натч умеет на эту тему, НО Я НЕ ПРОВЕРЯЛ :-)
к тому же индекс цитирования может, Вам, и не нужен и вполне хватит мерджа результатов с нескольких машин. Кстати, натч (nutch) насколько я понимаю достаточно шустро работает.
Deleon, я могу еще догадаться, что такое дедикейтед. Это, кстати, более или менее устоявшийся термин. Но вот, пёрсонал айпи смахивает на бред больного воображения. По-крайней мере, я этот термин впервые слышу и не понимаю, что это значит, хотя очень хочу, раз уж гуглевый бот плохо такие айпи кушает.
ааа, кажется, я догадался personal == динамический??? верно?
так у сайта тоже может быть динамический айпи.
не сочтите за занудство, но я не знаком с такой терминологией. бывает сетка внутренняя, так там айпи может быть любой, а бывает сетка внешная, ака, интернет, так там разница только между ipv6 и ipv4.
Deleon, малина в Марьиной роще!!! А лично я не понимаю чем два айпи могут отличаться друг от друга. :(
Пилот, спасибо за ссылочку, проблема в том, что она не работает, при попытке перейти на страничку с удалением URL я ввожу свой текущий мейл и гуль мне выдает (ржунемогу):
Remove your URL
An account with that email address already exists! Please enter a new email address. If you have an existing account, please enter your email and password in the boxes to the right.
Да, в общем-то, бог с ними со старыми страничками, они погоды не делают, это я просто пример привожу на тему тормознутости гугля. А вот мсн с яхой в последнее время действительно подмётки рвут по части скорости индексации. А вот старик гугль почил на лаврах :-)
PS (update): Может он, конечно, какое-то подтверждение по почте послал, сейчас проверю
