Веб-кролинг на основе теории статистических решений и прогнозирование изменения веб-страницы

Изобретение относится к устройствам анализа данных, в частности к системам и способам получения информации из сетевой системы с использованием распределенного веб-кролинга. Техническим результатом является облегчение упреждающего веб-кролинга в компьютерной среде. Аспекты изобретения предусматривают оценки, на основании прогноза, полезности и теории статистических решений, изменений в подмножествах веб-страниц, увеличивающие возможности веб-кролинга и гарантирующие поддержание актуальности информации веб-страниц. Кроме того, изобретение облегчает избирательный кролинг страниц с более высокой вероятностью изменения. 7 з.п. ф-лы, 11 ил.

 

Область, к которой относится изобретение

Настоящее изобретение, в целом, относится к анализу данных и, в частности, к системам и способам получения информации из сетевой системы с использованием распределенного веб-кролера.

Уровень техники

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

Обычно к информации, имеющейся на веб-сайтах и серверах, обращаются через веб-браузер, выполняющийся на веб-клиенте (например, компьютере). Например, веб-пользователь может развернуть веб-браузер и зайти на веб-сайт, введя "универсальный указатель ресурса" (URL) веб-сайта (например, веб-адрес и/или адрес в Интернете) в поле адреса веб-браузера и нажав клавишу "ввод" на клавиатуре или щелкнув мышью по кнопке "перейти". URL обычно включает в себя четыре информационных раздела, которые облегчают доступ: протокол (язык общения между компьютерами), который указывает набор правил и стандартов обмена информацией, местоположение веб-сайта, название организации, которая поддерживает веб-сайт, и суффикс (например, com, org, net, gov, и edu), который указывает тип организации.

В некоторых случаях, пользователю заранее известно имя сайта или сервера и/или URL сайта или сервера, к которому пользователь желает обратиться. В таких случаях, пользователь может зайти на сайт, как описано выше, введя URL в поле адреса и подключившись к сайту. Однако во многих случаях, пользователь не знает URL или имя сайта. Тогда пользователь использует поисковую машину, которая облегчает определение местонахождения сайта на основании ключевых слов, предоставленных пользователем. В общем случае поисковая машина состоит из выполнимых приложений или программ, которые выполняют поиск по содержимому веб-сайтов и серверов на предмет ключевых слов и возвращают список ссылок на веб-сайты и серверы, где найдены ключевые слова. В основном поисковая машина включает в себя "веб-кролер" (именуемый также "паук" или "робот"), который извлекает как можно больше документов (например, извлекая URL, связанные с документами). Затем эта информация сохраняется так, чтобы индексатор мог манипулировать извлеченными данными. Индексатор читает документы и создает индекс с приоритетом на основании ключевых слов, содержащихся в каждом документе, и других атрибутов документа. Соответствующие поисковые машины обычно применяют оригинальные алгоритмы для создания индексов, чтобы по запросу возвращались осмысленные результаты.

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

Огромный объем информации в Интернете, имеющийся на сегодняшний день, по-видимому, представляет непреодолимую преграду для эффективного веб-кролинга. Например, типичному веб-кролеру, пытающемуся каталогизировать каждую страницу в Интернете, потребуются недели или даже месяцы, чтобы обойти их все. Страница, обновленная сразу после кролинга, может месяцами повторно не подвергаться кролингу, в каковом случае информация, связанная со страницей, каталогизируется неточно, что, в свою очередь, приводит к снижению эффективности, с которой пользователь может получать информацию, релевантную к поиску. Таким образом, в уровне техники имеются неудовлетворенные потребности в системах и способах, которые повышают скорость и эффективность веб-кролинга.

Раскрытие изобретения

Ниже, в упрощенном виде, представлена сущность изобретения с целью обеспечения понимания основных принципов, лежащих в основе некоторых аспектов изобретения. Эта сущность не является исчерпывающим обзором изобретения. Она не призвана идентифицировать ключевые/критические элементы изобретения или ограничивать объем изобретения. Ее единственной задачей является представление некоторых идей изобретения в упрощенной форме в качестве прелюдии к более подробному описанию, представленному ниже.

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

Согласно аспекту изобретения изменение веб-страницы можно прогнозировать, чтобы облегчить определение, относящееся к приоритету кролинга страницы. Вероятность того, что веб-страница изменилась после последнего кролинга, можно определить путем анализа, например, информации истории изменений, относящейся к конкретной(ым) странице(ам), а также данных истории изменений, относящихся к другим страницам. Дополнительно, для прогнозирования, когда изменится страница, можно использовать различные особенности страницы. Например, можно анализировать URL страницы, чтобы определить, имеет ли он окончание ".html", ".com" и т.д. Аналогично, для прогнозирования изменения страницы можно обращаться к особенностям документа или HTML (например, содержит ли он таблицу, фотографию и т.д.). Кроме того, для прогнозирования, когда изменится страница, можно использовать особенности слов на странице и/или информации статуса HTTP, полученные при загрузке страницы.

Согласно еще одном аспекту изобретения для улучшения прогнозирования изменения веб-страниц можно обеспечить петли обратной связи/прямой связи. Этот аспект предусматривает создание выборочного множества URL и их кролинг с регулярными интервалами независимо от вероятности изменения, в целях подбора обучающих данных для обучения вероятностных предсказателей, для настройки параметров стратегий кролинга и т.д. Выборки можно взвешивать по значению, такое значение определяется, например, тем, сколько раз URL появился в результирующем множестве для пользовательского поиска, насколько часто щелкал по URL пользователь, который получил URL в результирующем множестве для поиска и т.д. Выборочное множество можно обновлять с регулярными интервалами, чтобы отдельные URL или подмножества URL можно было добавлять или удалять из выборочного множества, чтобы по истечении периода времени (например, месяца, двух месяцев и т.д.) выборочное множество могло быть совершенно новым. Альтернативно, выборочные множества можно полностью заменять согласно заданному расписанию.

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

Краткое описание чертежей

Фиг.1 - иллюстрация системы 100 веб-кролинга согласно аспекту настоящего изобретения.

Фиг.2 - иллюстрация системы 200 веб-кролинга согласно аспекту настоящего изобретения.

Фиг.3 - иллюстрация системы 300 веб-кролинга согласно аспекту настоящего изобретения, детализирующая взаимодействующие компоненты веб-кролинга.

Фиг.4 - иллюстрация системы 400 веб-кролинга согласно аспекту настоящего изобретения, детализирующая взаимодействующие компоненты веб-кролинга.

Фиг.5 - иллюстрация способа 500 согласно аспекту настоящего изобретения.

Фиг.6 - иллюстрация способа 600 согласно аспекту настоящего изобретения.

Фиг.7 - иллюстрация способа 700 согласно аспекту настоящего изобретения.

Фиг.8 - иллюстрация способа 800 согласно аспекту настоящего изобретения.

Фиг.9 - иллюстрация способа 900 согласно аспекту настоящего изобретения.

Фиг.10 и 11 - схемы иллюстративных вычислительных сред 1000 и 1100 согласно аспекту настоящего изобретения.

Осуществление изобретения

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

Используемый в данной заявке термин "компонент" обозначает сущность, относящуюся к компьютеру, либо оборудование, либо комбинацию оборудования и программного обеспечения, либо программное обеспечение, либо выполняющееся программное обеспечение. Например, компонент может представлять собой, но без ограничения, процесс, выполняющийся на процессоре, процессор, объект, выполняемый модуль, поток выполнения, программу и/или компьютер. В порядке иллюстрации компьютерным компонентом может быть как приложение, действующее на сервере, так и сервер. Один или несколько компонентов могут размещаться в процессе и/или в потоке выполнения, и компонент может размещаться на одном компьютере и/или быть распределен между двумя или более компьютерами. "Поток" это сущность в процессе, которую ядро операционной системы планирует для выполнения. Как известно из уровня техники, с каждым потоком связан "контекст", который представляет собой изменяющиеся данные, связанные с выполнением потока. Контекст потока включает в себя содержимое системных регистров и виртуальные адреса, принадлежащие процессу потока. Таким образом, фактические данные, содержащие контекст потока, изменяются по мере его выполнения.

Настоящее изобретение обеспечивает усовершенствованные системы и способы поддержания индекса веб-документов. Его также можно использовать для извлечения и поддержания данных для других типов информации. Традиционные веб-кролеры имеют определенные недостатки, которые настоящее изобретение позволяет ослабить. На каждом клиенте (например, машине любого человека, который осуществляет доступ к "паутине") хранится локальная информация, поэтому он может определять, изменилась ли веб-страница после последнего посещения клиента. Если она изменилась, то клиент может передать эту информацию поисковой машине. Аналогично сервер может использовать информацию о веб-страницах, посещенных клиентами, чтобы найти страницы, в настоящее время не известные серверу. Эффективное нахождение документов и поддержание оперативной информации об этих документах является чрезвычайно важной задачей для поиска как в интрасети, так и в Интернете. Настоящее изобретение также можно использовать в таких контекстах, как поиски в интрасети, кролинг страниц и постоянное обновление информации страниц на сервере является еще более сложной задачей.

Важным компонентом поисковой машины (для Интернета, интрасети и пр.) является кролер данных или веб-кролер. Веб-кролер работает в двух главных направлениях: отыскивает неизвестные документы, подлежащие индексации поисковой машиной, и пытается гарантировать, что располагает оперативной информацией о каждом известном документе. Обе эти задачи сложны и (совместно с качеством технологии "ПейджРэнк") входят в число наиболее важных и заметных признаков различия между поисковыми машинами. Кролеры документов обычно базируются на модели сервера. Поисковая машина осуществляет кролинг "паутины" посредством топологического поиска. Начиная с затравочного множества известных веб-страниц, кролер следует по ссылкам от этих страниц и, таким образом, может находить все веб-страницы, связанные посредством пути (множество ссылок по URL) из затравочного множества. Чтобы гарантировать, что поисковая машина располагает оперативной информацией о коллекции документов, кролинг нужно часто повторять. Поскольку кролер повторно посещает веб-страницы при каждом выполнении кролинга, он может определять, насколько часто изменяется страница (или подстраница), и выполнять повторный кролинг определенных страниц чаще других на основании, например, исторической информации о частоте изменения, прогнозируемых будущих изменениях и т.д.

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

Используемый здесь термин "вывод" относится, в целом, к процессу рассуждения о состояниях системы, среды и/или пользователя или делании выводов о них на основании множества наблюдений, воспринимаемых посредством событий и/или данных. Вывод может применяться, например, для идентификации конкретного контекста или действия или может генерировать распределение вероятности по состояниям. Вывод может быть вероятностным, т.е. вычислением распределения вероятности по интересующим состояниям с учетом данных и событий. Вывод также может относиться к методам, применяемым для составления событий более высокого уровня из множества событий и/или данных. Такой вывод приводит к построению новых событий или действий из множества наблюденных событий и/или сохраненных данных события, вне зависимости от того, коррелируют ли события в тесной временной близости и поступают ли события и данные из одного или нескольких источников событий и данных.

На фиг.1 показана система 100, которая обеспечивает предсказательный подход к назначению приоритетов страницам для кролинга. Система 100 содержит компонент 102 веб-кролинга, который просматривает веб-страницы с целью обнаружения и обновления страниц в каталоге возможных результатов поиска. Компонент 102 веб-кролинга оперативно связан со связывающим компонентом 104, который распределяет веб-страницы по множествам или "порциям" одинакового приоритета на основании полезности страниц. Связывающий компонент 104 также оперативно связан с поисковым сервером 106, который содержит подмножества из таких элементов, как URL, которые могут быть выбраны управляющим компонентом 108 для осуществления кролинга кролинговым компонентом 102. Таким образом, поисковый сервер 106 может подвергаться кролингу кролинговым компонентом 102 и непрерывно подвергаться повторному назначению приоритетов посредством связывающего компонента 104.

Система 100 облегчает прогнозирование изменения веб-страницы с целью ускорения кролинга веб-страницы после изменения, чтобы поисковый сервер мог обновляться без существенной задержки. Такое прогнозирование можно производить, оценивая вероятность изменения страницы после последнего посещения кролера. Чтобы определить вероятность изменения страницы, можно оценить историческую информацию, относящуюся к конкретным страницам (например, сколько раз страница изменилась в прошлом, степень изменения и т.д.), а также исторические данные, относящиеся к изменениям других страниц. Кроме того, можно использовать особенности URL страницы (например, оканчивается ли URL на ".html", ".com" и т.д.), особенности документа или HTML (например, содержит ли он таблицу, фотографию и т.д.), особенности слов на странице и/или информацию статуса HTTP, полученные при загрузке страницы.

Управляющий компонент 104 может строить статистическую модель для прогнозирования вероятностей, связанных с изменениями веб-страниц. Такая статистическая модель может представлять собой, например, логистическую регрессию, вероятностную версию машины векторов поддержки и т.д. Для построения статистической модели управляющий компонент 106 может собирать обучающие данные, подходящие для хронирования изменения веб-страниц (и, в более общем случае, других аспектов, которые описывают возможные исходы, например, количества просмотров страницы, степени изменения и т.д.) для множества страниц, а также конкретную историю изменений каждой страницы. Управляющий компонент 106 может также строить обучающее множество, извлекая особенности каждой страницы с использованием содержимого страницы, истории изменения страницы, ее URL, сообщений о статусе HTTP, связанные с загрузкой страницы и т.д. В случае прогнозирования сценария "новая страница" управляющий компонент 104 может использовать подмножество этой информации (например, в котором отсутствует историческая информация).

Согласно еще одному аспекту изобретения система 100 может использовать прогнозирование изменения веб-страницы для поддержки избирательной загрузки страниц теории статистических решений для максимизации эффективности кролингового компонента 102 в обнаружении и обновлении измененных веб-страниц. Для облегчения выбора на основе теории статистических решений надлежащего времени кролинга конкретной страницы можно использовать различные факторы. Например, такие факторы могут содержать множество возможных действий, А; множество возможных исходов, О; вероятность наступления конкретного исхода, Pr; и коэффициент полезности, связанный с каждым исходом, Utility(O), который воспринимает значение конкретного исхода. Такие факторы можно использовать для выбора наилучшего действия путем применения принципала максимальной ожидаемой полезности. Пусть, например, выбрано действие a ∈ A, при котором значение

достигает максимума.

Множество всех действий А может содержать все возможные подмножества страниц, которые можно загрузить в поисковый сервер 106. Каждую отдельную страницу можно рассматривать независимо от других страниц с целью упрощения выбора действия, и множества страниц можно выбирать на основании их собственного ранжирования. Этот подход облегчает принятие решений относительно того, какие страницы обновлять в текущий период времени, и смягчает проблемы, связанные со временем, необходимым для кролинга каждой страницы, которое может составлять недели или месяцы.

Для каждого выбранного действия возможны несколько исходов О. Например, исход может состоять в решении не загружать страницу, в неудачной попытке загрузки страницы, в загрузке неизмененной страницы и/или в загрузке измененной страницы. Варианты возможных исходов можно расширить так, чтобы они содержали другие аспекты, например сколько раз страница может быть просмотрена в течение наступающего периода времени (например, недели, месяца и т.д.), степень изменения страницы и т.д.

Функция полезности взвешивает значение каждого исхода, так что значение страницы может быть функцией важности страницы, количества просмотров страницы за данный период времени, количества щелчков мышью по странице, конкретных ссылок, по которым щелкали мышью на странице, степени изменения в измененной странице, различных деловых регламентов (например, кролинг каждой страницы раз в 4 недели, кролинг страницы, самое большее, ежедневно и т.д.) и/или любого другого подходящего аспекта, связанного с важностью страницы.

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

Избирательный кролинг такого обширного множества страниц требует стратегии для определения страниц, подлежащих кролингу в текущий и будущие периоды времени. Например, если просматриваемая страница является новой страницей, управляющий компонент 108 не располагает никакими историческими данными, на основе которых можно прогнозировать вероятность изменения страницы. Согласно этому примеру управляющий компонент может опираться на содержимое страницы, URL страницы и т.д. Если страница не новая, то управляющий компонент может обратиться к имеющейся истории изменений страницы помимо информации, описанной выше применительно к новой странице. Кроме того, теория принятия решения может также облегчать более частый кролинг новой страницы с целью пополнения и/или получения информации о частоте изменения страницы. Например, если вероятностный предсказатель указывает, что он является неопределенным в своем прогнозе изменения страницы, то на основе теории статистических решений можно выбрать осторожный вариант и осуществлять кролинг страницы часто, снижая, таким образом, опасность того, что страница станет неприемлемо устаревшей, и обеспечивая больше исторических данных, что может повысить определенность будущих прогнозов вероятности.

Кроме того, управляющий компонент 108 может предписывать кролинговому компоненту 102 осуществлять кролинг в зависимости от категорий, используя такие категории, как "бейсбол", "биржевой курс" и т.д. Таким образом, кролинговый компонент 102 может избирательно осуществлять кролинг страниц, содержащих указания конкретной категории. Аналогично, управляющий компонент 108 может предписывать кролинговому компоненту 102 осуществлять кролинг в зависимости от запроса (например, "Australian Open", "StockX" и т.д). Такие примеры представляют темы, информация по которым изменяется часто и, следовательно, веб-страницы, связанные с этими темами, будут часто обновляться (например, счета, цены и т.д.). Такой кролинг в зависимости от запроса может повышать эффективность прогнозирования изменения веб-страницы. Кроме того, пространство исходов можно расширить, чтобы оно содержало количество просмотров страницы в будущий период времени, количество и/или степень изменения страницы и т.д.

На фиг.2 показана система 200, которая связывает URL в соответствии с их полезностью, согласно аспекту изобретения. Управляющий компонент 202 может загружать порции веб-страниц с поискового сервера 204. Порция может представлять собой, например, 65,536 страниц, 32,768 страниц или какое-либо другое количество веб-страниц, сгруппированных друг с другом. Управляющий компонент 202 подбирает информацию из подмножеств загруженных порций, причем каждое подмножество содержит, по меньшей мере, одну веб-страницу. Информация, подобранная управляющим компонентом 202 может содержать, например, содержимое страницы, URL, информацию заголовка HTTP, историческую информацию и т.д. Управляющий компонент 202 может затем спрогнозировать вероятность того, что конкретная страница или подмножество страниц изменилась после предыдущего кролинга или изменится до следующего запланированного кролинга, и предписать веб-кролеру 204 предпринять действие, способствующее нужному исходу (например, осуществить кролинг страницы, если изменение неизбежно, игнорировать страницу до запланированного кролинга, поскольку изменение маловероятно, и т.д.). Кроме того, можно делать прогнозы относительно хронирования изменения страницы и/или вероятности того, что страница изменится в конкретный день в будущем или изменилась в конкретный день в прошлом. Такие прогнозы можно применять для обеспечения кривой распределения, выражающей вероятности того, что страница изменится к одной из указанных дат. Такие прогнозы могут определять, какой порции должна принадлежать страница.

После того как выбранные страницы были подвергнуты кролингу и была обновлена соответствующая информация, связывающий компонент 208 может получить информацию URL от веб-кролера 206 переупаковать URL в новые порции (ПОРЦИИ*) на основании прогнозов, например, когда страница(ы) измени(я)тся. Затем связывающий компонент 208 может восстановить переупакованные ПОРЦИИ* в поисковом сервере 204.

На фиг.3 показаны компоненты описанного здесь веб-кролера согласно аспекту изобретения. Показано, что циклический компонент 302 осуществляет кролинг перечисленных страниц, 1-n, по отдельности сверху вниз, что указано пунктирными стрелками, направленными вертикально вниз. Таким образом, циклический компонент гарантирует, что каждая страница будет подвергнута кролингу в течение конкретного периода кролинга (например, 28 дней), что, в свою очередь, гарантирует, что ни одна страница не устареет более чем на 28 дней. Следует понимать, что период кролинга может представлять собой любой период времени, достаточный для кролинга поискового сервера, и не ограничивается периодом в 28 дней.

Согласно фиг.3 циклический компонент 302 подверг кролингу Порцию 1 (что указано обозначением "RR" в левом нижнем углу Порции 1) и находится в процессе кролинга Порции 2. По завершении кролинга Порции 2 циклический компонент 302 может перейти к кролингу Порции 3, чтобы определить ее содержимое. Однако жадный компонент 304 находится в процессе кролинга Порции 3, и поэтому циклический компонент 302 может получить указание, что Порция 3 не требует кролинга. Таким образом, следующая порция, которую подвергнет кролингу циклический компонент 302, это Порция 4. Заметим, что жадный компонент 304 уже подверг кролингу порцию N и что пунктирные вертикальные стрелки, связанные с жадным компонентом, проходят в обоих направлениях по списку порций в множестве, демонстрируя, что жадный компонент 304 не ограничен порядком порций при кролинге. Напротив, жадный компонент 304 может выбирать порции (которые могут быть отдельными страницами) для кролинга на основании наилучшего показателя, например показателя прогнозирования (например, максимальной средней вероятности изменения после последнего кролинга), показателя полезности (например, максимальной средней полезности) и/или показателя на основе теории статистических решений (например, максимальной ожидаемой полезности) и т.д. Таким образом, циклический компонент 302 может гарантировать, что все порции подвергаются кролингу в течение предписанного периода времени, тогда как жадный компонент гарантирует, что в порциях с наивысшими показателями полезности и/или потенциала изменения поиск производится раньше, чем в порциях с более низкими показателями. Кроме того, способность циклического компонента 302 распознавать, что порция была подвергнута кролингу жадным компонентом 304 в течение текущего периода кролинга, сокращает время, необходимое для кролинга порции, поискового сервера и т.д. Алгоритмы, описывающие, каким образом взаимодействуют циклический компонент 302 и жадный компонент 304, описаны ниже со ссылкой на фиг.7-9.

На фиг.4 показаны компоненты веб-кролера, описанного здесь согласно аспекту изобретения. На фигуре циклический компонент 402 показан на периметре порции (например, подмножестве элементов или страниц и т.д.), чтобы продемонстрировать упорядоченный кролинг порции, осуществляемый циклическим компонентом 402. Показано, что циклический компонент 402 подверг кролингу Порцию 1 и находится в процессе кролинга Порции 2. Порции 1 и 2 показаны с "RR" в правом нижнем углу, чтобы указать, что каждая порция была подвергнута или в данный момент подвергается кролингу циклическим компонентом 402. Жадный компонент 404 показан в центре порций, чтобы наглядно продемонстрировать, что жадный компонент 404 имеет доступ ко всем порциям безотносительно к их циклическому упорядочению. Например, жадный компонент в данный момент осуществляет кролинг Порции 3, что обозначено в виде канала связи, соединяющего жадный компонент 404 с Порцией 3. Заметим однако, что Порция 5 уже была подвергнута кролингу жадным компонентом 404, несмотря на тот факт, что Порция 5 располагается после Порции 3. Согласно этому примеру жадный компонент 404 определил, что Порция 5 имеет более высокий показатель (например, прогнозирования, полезности и/или на основе теории статистических решений и т.д.), чем Порция 3, и потому подверг кролингу Порцию 5 до Порции 3. Циклический компонент 402 может попытаться осуществить кролинг Порции 3 по завершении кролинга Порции 2, но может распознать, что Порция 3 была подвергнута кролингу жадным компонентом 404. Таким образом, следующая порция, которую подвергнет кролингу циклический компонент, будет Порция 4.

Несмотря на то что в целях простоты объяснения один или несколько способов, показанные здесь, например, в виде логической блок-схемы, показаны и описаны как последовательность действий, понятно и очевидно, что настоящее изобретение не ограничивается порядком действий, поскольку действия могут, согласно настоящему изобретению, происходить в другом порядке и/или одновременно с другими действиями из тех, которые показаны и описаны здесь. Например, специалистам в данной области понятно и очевидно, что способы можно альтернативно представить в виде последовательности взаимосвязанных состояний или событий, например, в диаграмме состояний. Кроме того, не все показанные действия могут потребоваться для реализации способа согласно настоящему изобретению.

На фиг.5 представлен способ предсказательного веб-кролинга посредством жадного алгоритма согласно аспекту изобретения. На этапе 502 порции загружаются с поискового сервера с целью кролинга. На этапе 504 показатели порций определяются для облегчения определения, какие порции подвергать кролингу. Например, показатель порции может представлять собой показатель прогнозирования (например, максимальную среднюю вероятность изменения после последнего кролинга), показатель полезности (например, максимальную среднюю полезность) и/или показатель на основе теории статистических решений (например, максимальную ожидаемую полезность) и т.д. Если показатель данной порции не гарантирует жадный кролинг, то порция не будет немедленно подвергнута кролингу. Если показатель порции достаточно высок, чтобы гарантировать жадный кролинг, то на этапе 508 порции с достаточными показателями могут быть подвергнуты кролингу.

На фиг.6 показан способ согласно аспекту настоящего изобретения, в котором количество порций, выбранных для кролинга, может определяться, например, емкостью кролинга. На этапе 602 определяется емкость кролинга для веб-кролера (например, оценивается максимальное количество М порций, которые возможно подвергнуть кролингу). На этапе 604 порции можно загрузить с поискового сервера для потенциального кролинга. На этапе 606 можно определить показатели порций (например, прогнозирования, на основе полезности и/или на основе теории статистических решений) для облегчения определения, какие порции подвергать кролингу. На этапе 608 можно произвести определение в отношении показателей порций и гарантирует ли показатель данной порции жадный кролинг (например, должен ли кролер осуществлять кролинг в опережение расписания, и т.д.). Если показатель данной порции не гарантирует жадный кролинг, то порция не будет немедленно подвергнута кролингу. Если показатель порции достаточно высок, чтобы гарантировать жадный кролинг, то на этапе 508 порции с наилучшими показателями могут быть подвергнуты кролингу.

На фиг.7 представлен способ 700 согласно аспекту настоящего изобретения, в котором жадный алгоритм используется совместно с циклическим алгоритмом. Этот аспект изобретения предусматривает использование жадного алгоритма для выбора порций с использованием показателей прогнозирования, на основе полезности и/или на основе теории статистических решений, в то же время гарантируя, что все порции могут быть подвергнуты кролингу (в будущем) до того, как они устареют на D дней. На этапе 702 производится определение относительно того, какой процент емкости кролинга нужен циклическому алгоритму (rr%), чтобы гарантировать, что ни один URL не устарел более чем на D дней (например, чтобы гарантировать, что все страницы будут подвергнуты кролингу, по меньшей мере, раз в D дней). Например, если 50% имеющейся емкости кролинга могут, с использованием циклического алгоритма, гарантировать, что ни одна порция не устареет более чем на 28 дней, то циклический алгоритм может осуществлять кролинг порций согласно их крайним срокам. Крайние сроки можно определить, например, оценив, когда порция была последний раз подвергнута кролингу. Например, если порция А подверглась кролингу 14 дней назад, то ее крайний срок наступит через 14 дней. Если порция В подверглась кролингу 7 дней назад, то ее крайний срок наступит через 21 день. Таким образом, порция A подвергнется кролингу до порции В. Согласно этому примеру 50% емкости кролинга можно назначить циклическому алгоритму на этапе 704.

На этапе 706 остаток емкости кролинга (1-rr%) можно назначить жадному алгоритму (g%) для жадного кролинга. Затем, на этапе 707, можно определить максимальное количество (M) порций, которые могут быть подвергнуты кролингу в период времени, например, оценив размер порций, подлежащих выбору, и продолжительность периода времени, причем скорость кролинга является известным значением. На этапе 710 можно произвести определение относительно того, какие конкретно порции должны быть подвергнуты кролингу (TBC). Затем, на этапе 712, выбирается нижняя граница для количества порций с наилучшими показателями, подлежащих добавлению в TBC, с использованием формулы g%*M. Например, если g%=55% и М равно 5, то g%*M равно 2,75, и нижняя граница будет 2. Наконец, на этапе 714, производится выбор старейших порций по формуле М-размер(ТВС), каковые порции добавлены в ТВС. Таким образом, порции выбираются для жадного кролинга, тогда как циклический алгоритм гарантирует, что все порции будут подвергнуты кролингу в течение данного периода времени.

На фиг.8 представлен способ 800 согласно аспекту настоящего изобретения, в котором жадный алгоритм используется совместно с циклическим алгоритмом. На этапе 802 производится определение относительно того, какой процент емкости кролинга нужен циклическому алгоритму (rr%), чтобы гарантировать, что ни один URL не устарел более чем на D дней (например, чтобы гарантировать, что все страницы будут подвергнуты кролингу, по меньшей мере, раз в D дней). Затем, на этапе 804, емкость кролинга можно выделить циклическому алгоритму. На этапе 806 остаток емкости кролинга (1-rr%) можно назначить жадному алгоритму (g%) для жадного кролинга. Затем, на этапе 808, можно определить максимальное количество (M) порций, которые могут быть подвергнуты кролингу в период времени, например, оценив размер порций, подлежащих выбору, и продолжительность периода времени, причем скорость кролинга является известным значением. На этапе 810 производится определение в отношении того, какие конкретные порции подлежат кролингу (ТВС).

На этапе 812 верхняя граница выбирается на основании формулы rr%*M для количества порций, подлежащих добавлению к ТВС. Например, если rr% равно 53% и М равно 10, то rr%*M равно 5,3 и результирующее значение верхней границы будет 6. На этапе 814 старейшие М-размер(ТВС) порции с наилучшими показателями (например, прогнозирования, полезности и/или на основе теории статистических решений и т.д.) выбираются и добавляются в ТВС. Таким образом, порции выбираются для жадного кролинга, в то время как циклический алгоритм гарантирует, что все порции будут подвергнуты кролингу в течение данного периода времени.

На фиг.9 представлен способ 900 согласно аспекту настоящего изобретения, в котором жадный алгоритм используется совместно с циклическим алгоритмом. Возможно, что циклический алгоритм может закончить кролинг всех порций быстрее, чем это требуется при использовании вышеописанных способов. Это может произойти потому, что жадный алгоритм также осуществляет кролинг порций. Например, если все порции нужно подвергнуть кролингу в течение 28-дневного периода, применение способов 700 или 800 может привести к тому, что все страницы фактически подвергаются кролингу в течение 20 дней. Ниже подробно рассмотрен алгоритм, позволяющий учесть этот возможный случай.

Пусть С это множество порций и C0,C1,...,Cn - разбиение С, где Cj - порции, соответствующие j периодам времени, Nj - количество порций в Cj. Количество членов в разбиении (например, n) множества С является функцией максимально допустимого устаревания. Пусть L это максимальное количество порций, которые желательно подвергнуть кролингу в течение периода времени (например, чтобы гарантировать, что ни одна порция не устареет больше чем на D дней), и пусть М - максимальное количество порций, которые можно подвергнуть кролингу в течение периода времени, где М больше или равно L. Пусть ТВС это множество порций, подлежащих кролингу в текущий период времени. Заметим, что в нижеприведенном цикле "for" R используется для хранения количества порций, которые должны быть подвергнуты кролингу после текущего дня со сроком выполнения <j, и PQ это очередь по приоритету порций, приоритет которых назначен по показателю порции.

Присвоить каждой порции показатель (прогнозирования, полезности или на основе теории статистических решений); TBC = C0; Инициализировать PQ = {}; For j = 1 to n { Добавить порции в Cj в очередь по приоритету PQ; While (размер(PQ)>j*L) //превышение емкости поэтому согласование с емкостью путем сдвига элемента(ов) { Переместить верхний элемент из PQ в TBC } } // Выбрать порции для заполнения емкости кролинга While(размер(TBC)<M) { Переместить верхний элемент из PQ в TBC } Return TBC; }

Согласно фиг.9, на этапе 902, каждой порции C0...Cn присваивают вышеописанный показатель (например, прогнозирования, полезности и/или на основе теории статистических решений). На этапе 904 порции сортируют по срокам выполнения (например, порции, подлежащие кролингу во время j, содержатся во множестве Cj, которое имеет Nj порций). На этапе 906 порции в Cj добавляются в очередь по приоритету (PQ). Затем, на этапе 908, производится определение размера PQ по отношению к значению j*L, где L - максимальное желаемое количество порций, подлежащих кролингу. Если PQ меньше j*L, то такую информацию можно использовать для обеспечения обратной связи и способ может возвратиться к этапу 906 для дальнейшего добавления порций. Если PQ больше j*L, то на этапе 910 верхнюю порцию в PQ можно переместить в множество порций, подлежащих кролингу (TBC). На этапе 912 производится определение размера ТВС по отношению к М, где М - максимальное количество порций, которые можно подвергнуть кролингу в течение периода времени. Если ТВС меньше М (например, в ТВС остается место для других порций, и т.д.), то способ может возвратиться к этапу 910 для перемещения следующей верхней порции из PQ в TBC. Если на этапе 912 определено, что размер ТВС не меньше М, то на этапе 914 TBC может быть возвращено веб-кролеру для кролинга. Таким образом, статус порции и крайние сроки кролинга можно непрерывно обновлять с целью извлечения выгоды в случае, когда циклический и жадный алгоритмы совместно осуществляют кролинг за меньшее время, чем требуется.

Очевидно, что настоящее изобретение допускает применение петли(ель) обратной связи в сочетании с прогнозированием изменений веб-страниц. Например, помимо вышеописанного регулярного кролинга, отдельные URL можно выбирать и подвергать кролингу с регулярными интервалами, независимо от вероятности изменения, для обеспечения обучающих данных для обучения вероятностных предсказателей и для настройки стратегий кролинга. Это также может обеспечивать данные, которые могут облегчать тестирование стратегий кролинга, построение метрик для такого тестирования и проверки методов кролинга. Например, размер выборки в 64,000 URL может быть достаточно большим, чтобы быть полезным, и выборки не обязаны быть однородными по всем URL, но могут взвешиваться по значению. Согласно одному аспекту значение выборки можно определить путем отбора URL из результирующего множества, отправленного пользователям, которые используют данную поисковую машину. Кроме того, информацию, доступную по щелчку мыши, можно использовать для облегчения определения предложенных URL, по которым щелкают пользователи, чтобы придать таким URL больший вес, чем другим выборкам в результирующем множестве.

Интервал кролинга можно согласовать с максимальной частотой эпизодов кролинга в производственной среде (например, ежедневно, ежечасно, и т.д.). Очевидно, что настоящее изобретение не ограничивается такими интервалами. Кроме того, может быть полезен случайный кролинг, поскольку он не зависит от стратегии производства кролинга.

Страницы в выборке также можно подвергать кролингу нормальным путем. Согласно этому аспекту URL не нужно перемещать в эту выборку, но можно копировать в нее. Периодически (например, каждый месяц, каждые два месяца и т.д.) можно брать новую выборку. Альтернативно, URL можно равномерно добавлять и удалять, чтобы через месяц (или два, т.д.) выборка была новой по сравнению с предыдущим месяцем. Согласно этому аспекту можно удерживать больший объем данных о каждом URL, чем при регулярном кролинге. Например, регулярный кролинг может допускать удержание только количества раз, когда изменялась веб-страница, количества раз, когда она оставалась прежней и/или средний интервал между посещениями веб-страницы кролером. Однако описанные здесь протоколы обратной связи могут допускать удержание информации, указывающей, например, изменилась ли веб-страница в данный день. Кроме того, для каждого URL в выборке можно поддерживать записи относительно его первоначальных условий (например, информацию о конкретной странице, подобранной в ходе регулярного кролинга). Таким образом, для того чтобы предположить, что каждый URL в выборке является новым URL, не требуется моделирование веб-кролинга. Таким боразом, стратегии веб-кролинга можно усовершенствовать, чтобы повысить свежесть страниц с более высокой частотой изменения относительно страниц, которые изменяются нечасто, что, в свою очередь, облегчает применение значительно меньшего количества машин для получения значительно более свежих результатов.

В целях обеспечения дополнительного контекста для реализации различных аспектов настоящего изобретения фиг.10 и нижеследующее рассмотрение обеспечивают краткое, обобщенное описание подходящей вычислительной среды 1000, в которой могут быть реализованы различные аспекты настоящего изобретения. Хотя изобретение описано выше в общем контексте компьютерно-выполняемых команд компьютерной программы, которая выполняется на локальном компьютере и/или удаленном компьютере, специалистам в данной области очевидно, что изобретение также можно реализовать в сочетании с другими программными модулями. В общем случае программные модули включают в себя процедуры, программы, компоненты, структуры данных и т.д., которые выполняют определенные задачи и/или реализуют определенные абстрактные типы данных. Кроме того, специалистам в данной области очевидно, что способы, отвечающие изобретению, можно осуществлять на практике с другими конфигурациями компьютерной системы, включая однопроцессорные или многопроцессорные компьютерные системы, мини-компьютеры, универсальные компьютеры, а также персональные компьютеры, карманные вычислительные устройства, бытовую электронику на основе микропроцессора и/или программируемую бытовую электронику и т.д., каждая из которых может оперативно поддерживать связь с одним или несколькими соответствующими устройствами. Проиллюстрированные аспекты изобретения также можно осуществлять на практике в распределенных вычислительных средах, где определенные задачи выполняются удаленными вычислительными устройствами, связанными посредством сети связи. Однако некоторые, если не все, аспекты изобретения можно практически осуществлять на автономных компьютерах. В распределенной вычислительной среде программные модули могут размещаться в локальных и/или удаленных запоминающих устройствах. Используемый в данной заявке термин "компонент" обозначает сущность, относящуюся к компьютеру, либо оборудование, либо комбинацию оборудования и программного обеспечения, либо программное обеспечение, либо выполняющееся программное обеспечение. Например, компонент может представлять собой, но без ограничения, процесс, выполняющийся на процессоре, процессор, объект, выполняемое, поток выполнения, программу и/или компьютер. В порядке иллюстрации, компьютерным компонентом может быть как приложение, действующее на сервере, так и сервер. Кроме того, компонент может включать в себя один или несколько подкомпонентов.

Согласно фиг.10 иллюстративная системная среда 1000 для реализации различных аспектов изобретения включает в себя традиционный компьютер 1002, содержащий блок обработки 1004, системную память 1006 и системную шину 1008, которая подключает различные системные компоненты, включая системную память, к блоку обработки 1004. Блок обработки 1004 может представлять собой любой коммерчески доступный или оригинальный процессор. Кроме того, блок обработки может быть реализован как мультипроцессор, образованный более чем одним процессором, которые могут быть соединены параллельно.

Системная шина 1008 может относиться к любому из нескольких типов шинной структуры, включая шину памяти или контроллер памяти, периферийную шину и локальную шину, использующих любую из различных традиционных шинных архитектур, как то PCI, VESA, MicroChannel, ISA и EISA и т.д. Системная память 1006 включает в себя постоянную память (ПЗУ) 1010 и оперативную память (ОЗУ) 1012. Базовая система ввода/вывода (BIOS) 1014, содержащая базовые процедуры, которые помогают переносить информацию между элементами компьютера 1002, например, при запуске, хранится в ПЗУ 1010.

Компьютер 1002 может также содержать, например, жесткий диск 1016, привод 1018 магнитного диска, например, для чтения или записи сменного диска 1020 и привод 1022 оптического диска, например, для чтения или записи диска 1024 CD-ROM или иного оптического носителя. Жесткий диск 1016, привод 1018 магнитного диска и привод 1022 оптического диска подключены к системной шине 1008 посредством интерфейса 1026 жесткого диска, интерфейса 1028 привода магнитного диска и интерфейса 1030 привода оптического диска соответственно. Приводы 1016-1022 и соответствующие компьютерно-считываемые носители обеспечивают энергонезависимое хранение данных, структур данных, компьютерно-выполняемых команд и т.д. для компьютера 1002. Хотя вышеприведенное описание компьютерно-считываемых носителей относится к жесткому диску, сменному магнитному диску и CD, специалистам в данной области понятно, что другие типы носителей, считываемых компьютером, например магнитные кассеты, карты флэш-памяти, цифровые видеодиски, картриджи Бернулли и т.п., также могут использоваться в иллюстративной операционной среде 1000, а также, что любые такие носители могут содержать компьютерно-выполняемые команды для осуществления способов настоящего изобретения.

В приводах 1016-1022 и ОЗУ 1012 может храниться ряд программных модулей, включая операционную систему 1032, одну или несколько прикладных программ 1034, другие программные модули 1036 и программные данные 1038. Операционная система 1032 может представлять собой любую подходящую операционную систему или комбинацию операционных систем. Например, прикладные программы 1034 и программные модули 1036 могут включать в себя облегчающие клиентский веб-кролинг согласно аспекту настоящего изобретения.

Пользователь может вводить команды и информацию в компьютер 1002 посредством одного или нескольких устройство ввода, как то клавиатуры 1040 и указательного устройства (например, мыши 1042). Другие устройства ввода (не показаны) могут включать в себя микрофон, джойстик, игровой пульт, спутниковую антенну, беспроводной пульт дистанционного управления, сканер и т.п. Эти и другие устройства ввода часто бывают подключены к блоку обработки 1004 через интерфейс 1044 последовательного порта, который подключен к системной шине 1008, но могут подключаться и посредством других интерфейсов, например параллельного порта, игрового порта или универсальной последовательной шины (USB). Монитор 1046 или устройство отображения другого типа также подключен к системной шине 1008 через интерфейс, например видео-адаптер 1048. Помимо монитора 1046, компьютер 1002 может включать в себя другие периферийные устройства вывода (не показаны), как громкоговорители, принтеры и т.д.

Очевидно, что компьютер 1002 может работать в сетевой среде с использованием локальных соединений с одним или несколькими удаленными компьютерами 1060. Удаленный компьютер 1060 может представлять собой рабочую станцию, компьютер-сервер, маршрутизатор, равноправное устройство или другой общий сетевой узел и обычно включает в себя многие или все элементы, описанные в отношении компьютера 1002, хотя, для простоты, на фиг.10 показано только запоминающее устройство 1062. Логические соединения, обозначенные на фиг.10, могут включать в себя локальную сеть (ЛС) 1064 и глобальную сеть (ГС) 1066. Такие сетевые среды обычно широко распространены в учреждениях, компьютерных сетях в масштабе предприятия, интрасетях и в Интернете.

При использовании в сетевой среде ЛС компьютер 1002 может быть подключен к локальной сети 1064, например, посредством сетевого интерфейса или адаптера 1068. При использовании в сетевой среде ГС компьютер 1002 обычно содержит модем (например, для связи по телефонной линии, ЦАЛ, кабелю и т.д.) 1070, или подключен к серверу связи в ЛС, или имеет другое средство установления связи с ГС 1066, например Интернетом. Модем 1070, который может быть внутренним или внешним по отношению к компьютеру 1002, подключен к системной шине 1008 через интерфейс 1044 последовательного порта. В сетевой среде программные модули (включая прикладные программы 1034) и/или программные данные 1038 могут храниться в удаленном запоминающем устройстве 1062. Очевидно, что показанные сетевые соединения являются иллюстративными и что при осуществлении аспекта настоящего изобретения могут использоваться другие средства (например, проводные или беспроводные) установления канала связи между компьютерами 1002 и 1060.

Согласно практике специалистов в области компьютерного программирования настоящее изобретение было описано применительно к действиям и символическим представлениям операций, осуществляемых компьютером, например компьютером 1002 или удаленным компьютером 1060, если не указано иное. Такие действия и операции иногда называют компьютерно-выполняемыми. Очевидно, что действия и символически представленные операции включают в себя манипуляцию блоком обработки 1004 электрическими сигналами, представляющими биты данных, которая приводит к результирующему преобразованию или уменьшению представления электрического сигнала и к поддержанию битов данных в ячейках памяти системы памяти (включающей в себя системную память 1006, жесткий диск 1016, флоппи-диски 1020, CD-ROM 1024 и удаленную память 1062) с целью переконфигурирования или иного изменения работы компьютерной системы, а также другой обработки сигналов. Ячейки памяти, где поддерживаются биты данных, представляют собой физические ячейки, которые обладают определенными электрическими, магнитными или оптическими свойствами, соответствующими битам данных.

На фиг.11 показана другая блок-схема той же вычислительной среды 1100, с которой может взаимодействовать настоящее изобретение. Система 1100 дополнительно иллюстрирует систему, включающую в себя один или несколько клиент(ов) 1102. Клиент(ы) 1102 могут быть аппаратными и/или программными (например, потоками, процессами, вычислительными устройствами). Система 1100 также включает в себя один или несколько сервер(ов) 1104. Сервер(ы) 1104 также могут быть аппаратными и/или программными (например, потоками, процессами, вычислительными устройствами). Серверы 1104, например, могут заключать в себе потоки для выполнения преобразований путем использования настоящего изобретения. Одна возможная связь между клиентом 1102 и сервером 1104 может иметь вид пакета данных, адаптированного для передачи между двумя или более компьютерными процессами. Система 1100 включает в себя структуру 1108 связи, которую можно использовать для облегчения связи между клиентом(ами) 1102 и сервером(ами) 1104. Клиент(ы) 1102 оперативно подключены к одному или нескольким хранилищу(ам) 1110 данных клиента, которые можно использовать для локального хранения информации, локальной по отношению к клиенту(ам) 1102. Аналогично, сервер(ы) оперативно подключены к одному или нескольким хранилищу(ам) 1106 данных сервера, которые можно использовать для локального хранения информации, локальной по отношению к серверам 1104.

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

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

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

Специалистам в данной области также очевидно, что настоящее изобретение можно использовать не только для систем кролинга, основанных на взаимоотношениях клиент-сервер, но также для систем кролинга, основанных на взаимоотношениях между равноправными устройствами. Возможно также, что клиент может выполнять задачи, обычно связанные с "серверным" поведением, и таким образом переносить некоторые характеристики, связанные с сервером, на клиента в некоторых вариантах настоящего изобретения. Примером одного варианта настоящего изобретения является клиент, который осуществляет "субкролинг" в отношении других клиентов, чтобы получить и/или извлечь для отправки на сервер. Этот вариант может быть выгоден, например, в сетях, имеющих узкие места между определенными клиентами и сервером. Данные можно переносить на клиента с наилучшим доступом к серверу. В других вариантах настоящего изобретения, клиент может вести себя как сервер, инициируя субкролинги в интрасетевой системе, и, таким образом, выдавать информацию на сервер лишь от одного и/или существенно ограниченного количества клиентов, присутствующих в интрасети. Таким образом, поисковый сервер может инициировать множественные субкролинги на клиентах для расширения ресурсов кролинга.

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

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

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

3. Система по п.2, в которой компонент на основе теории статистических решений делает прогнозы, касающиеся изменений в, по меньшей мере, одной веб-странице, основываясь, по меньшей мере, частично, на множестве А возможных действий, подлежащих осуществлению на, по меньшей мере, одной веб-странице,
множестве О возможных исходов,
вероятности Pr наступления конкретного исхода и
коэффициенте полезности Utility(O), связанном с каждым исходом.

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

достигает максимума, где о это исход в множестве О всех возможных исходов.

5. Система по п.1, в которой упреждающий анализ базируется, по меньшей мере, частично, на полезности, по меньшей мере, одной веб-страницы.

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

7. Система по п.1, в котоой упреждающий анализ базируется, по меньшей мере, частично, на содержимом, содержащемся в, по меньшей мере, одной веб-странице.

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