Об оптимальном обходе сайтов спайдером

Предлагаю считать и сравнивать с хранимой контрольную сумму страницы .

Если она изменилась - идти вглубь по ссылкам и повторять этот алгоритм рекурсивно.

Если не изменилась - пройти по её ссылкам и проверить их CRC, если не изменились - то на этом успокоиться и процесс индексирования останавливать.

1) В HTTP запросе есть такой параметр if-modified-since или что-то около-того

2) По каждой из страниц можно считать как часто она меняется и в зависимости от этого увеличивать или уменьшать частоту выборки данной страницы. Будем примерно болтаться вокруг среднего времени обновления этой страницы. Бонус: необновляемые страницы будут обходиться все реже и реже. Например, мы выбирем страничку каждую неделю и почти всегда она за это время успевает измениться. Мы по некоторому эмпирическому правилу уменьшаем время обхода, скажем до 4 дней. Если при 4х дневных обходах она успевает измениться в большинстве случае, то еще сокращаем время. Грубо говоря, увеличивая и уменьшая частоту обхода можно примерно оценить время модификации страницы.

3) При обходе одного сайта (и кажись в RFC это есть) нужно делать задержки, иначе сайту может быть плохо. ИМХО не все поисковики так делают, а зря

PS:

4) Да и CRC надо дополнительно использовать для страниц, которым в качестве даты изменения возвращается дата выдачи страницы.

itman,

Мой вопрос собственно только в п.2 Вашего ответа. Остальное и так ясно. Только хотелось бы услышать, есть ли какие-либо "классические" алгоритмы решения этой задачи, описанные в литературе.

http://scholar.google.com/scholar?num=100&hl=en&lr=&q=index+freshness+crawl&btnG=Search

В частности,

Synchronizing a Database to Improve Freshness

J Cho, H Garcia-Molina кажется агитирует за последовательный обоход индекса, впрочем, я могу ошибаться, уже давно читал. В любом случае Гарсия-Малина крутой классик, worth reading.

а как в этом случае быть с динамически генерируемыми страницами? смотреть контрольную сумму? а если была просто изменена структура сайта, грубо говоря добавился еще один пункт в меню а содержимое страницы осталось неизменным? контрольная сумма при этом ведь изменится

я бы предложил примерно такую схему, при первой индексации страницы выделяете слова в нее входящие, сортируете их по частоте, из полученного ряда выбираете десяток другой слов расположенных в центре получившегося списка, это и будет ваша "контрольная сумма". при последующем обходе вы повторяете операцию и сравниваете полученный результат с сохраненным, в зависимости от него уже и выставляется время следующей индексации, либо оно уменьшается, либо увеличивается, в общем дальше идем по схеме itman-на

itman,

спасибо огромное! То что надо. Ушел гуглить..

А если у вас уже есть какие-то тексты, того же Гарсии, буду крайне признателен, если скинете что-нибудь на мыло basch @ yandex.ru.

В любом случае, спасибо!

так обратите внимание, они почти все в доступном виде есть (в гугльскаляре статьи группируются, в группе, если статья популярна бывают "бесплатные" pdf)

Из http://meta.math.spbu.ru/~nadejda/papers/web-ir/web-ir.html#SECTION00042000000000000000 :

• Edwards J., McCurley K., Tomlin J. An adaptive model for optimizing performance of an incremental web crawler. In Proc. of the WWW10, pp. 106-113, May 2001.
• Cho J., Garcia-Molina H. The Evolution of the Web and Implications for an Incremental Crawler. The VLDB Journal, pp. 200-209, 2000.
• Cho J., Garcia-Molina H. Synchronizing a database to improve freshness. In Proc. of the SIGMOD'00, pp. 117-128, 2000.

посвежее

• Index Freshness in Internet Search Engines
http://www.cs.uwaterloo.ca/~jlsocha/survey.ps
• Effective page refresh policies for Web crawlers
http://delivery.acm.org/10.1145/960000/958945/p390-cho.pdf
• Effective Web crawling
http://www.dcc.uchile.cl/~ccastill/crawling_thesis/effective_web_crawling.pdf

Тексты статей от Гарсиа-Молина почти все доступны на www.db.stanford.edu.

Заходим на http://dbpubs.stanford.edu:8090/aux/index-en.html и вводим слово crawler ...

да, всё нашел, спасибо itman и nis