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