СИСТЕМА, СПОСОБ И УСТРОЙСТВО ДЛЯ ОЦЕНКИ СЕАНСОВ ПРОСМОТРА

Перекрестная ссылка на родственные заявки

По настоящей заявке истребуется преимущество приоритета в отношении международной патентной заявки № PCT/RU 2013/000603, поданной 15 июля 2013 г., озаглавленной Система, способ и устройство для оценки сеансов просмотра, которая в полном объеме включена в данный документ.

Область техники

Область настоящего изобретения относится к системам, способам и алгоритмам ранжирования веб-страниц, в частности ранжирования веб-страниц в истории просмотра.

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

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

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

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

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

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

В этом способе первый коэффициент может быть математически связан со вторым коэффициентом.

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

В этом способе временные данные могут включать первый и второй моменты времени и интервал времени от первого момента времени до второго момента времени.

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

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

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

В этом способе первый момент времени и каждый момент времени могут разделить интервал времени на два или более подынтервала времени.

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

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

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

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

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

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

Этот способ может дополнительно включать: вычисление основанного на запросе запросо-зависимого ранжирования для веб-страницы; и вычисление объединенного ранжирования для веб-страницы как функции запросо-зависимого ранжирования и оценочного ранга.

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

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

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

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

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

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

Фиг. 2 является схематическим изображением отображения истории просмотра веб-сайта устройства, показанного на фиг. 1, и других устройств и преобразований истории просмотра в график и таблицу для анализа в соответствии с вариантом реализации изобретения;

Фиг. 3 является схематическим изображением устройства на фиг. 1 и его приложения для просмотра в соответствии с вариантом реализации изобретения;

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

Фиг. 5 является блок-схемой показательного алгоритма ранжирования просмотра, выполняемого приложением определения ранга страницы сервера поисковой системы на фиг. 1, в соответствии с вариантом реализации изобретения.

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

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

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

Во-первых, представлен пример сетей, в которых могут работать устройства, соответствующие варианту реализации изобретения. Как показано на фиг. 1, подробная информация по примеру системы сетей и устройств связи будет представлена согласно варианту реализации изобретения. На фиг. 1 показана система связи 100, в которой сеть 102 соединяет сервер поисковой системы 104 с другими серверами 106 (т.е. 106a и 106b) и устройством 108a посредством различных каналов связи. Сеть 112 может быть соединена с сетью 102 через канал связи (не показан), который может быть проводным или беспроводным и постоянным или временным. Устройство 108 подключено к сети 102 посредством канала связи 110, который может быть проводным или беспроводным, и постоянным или временным. Сеть 102 может быть сетью Интернет. Устройства, подключенные к сети 112, например устройство 108b, могут получать доступ к серверу поисковой системы 104 и другим серверам 106 посредством сети 112. По отношению к устройству 108, подключенному (прямо или косвенно) к сети 102, представлены два типичных сервиса: поисковые системы веб-сайта; и общий просмотр веб-сайта. Типичные особенности каждого сервиса будут кратко обсуждаться в порядке очереди.

Для использования сервиса просмотра через серверы 106 в сети 102 устройство 108b может просматривать различные веб-сайты в Интернете с помощью веб-браузера в своем графическом интерфейсе пользователя (ГИП). Типичный сеанс просмотра может иметь определенное событие открытия (например, открытие нового окна или вкладки просмотра в ГИП) и может иметь определенное событие закрытия (например, закрытие окна сеанса действием пользователя или самим браузером). Сеанс может считаться завершенным по истечении определенного периода времени, который определен для сеанса браузера на данном веб-сайте (например, 15 минут на текущем веб-сайте, отображаемом в браузере (например, www.yahoo.com), без какой-либо входной активности для изменения текущего веб-сайта устройством 108b). Когда веб-страница генерируется в браузере, по мере того как пользователь на устройстве 108b активирует гиперссылку на веб-странице, например, через устройство ввода (такое как мышь), которое связано с устройством 108 через гиперссылку на веб-странице, инициируется запрос на получение веб-страницы, связанной с гиперссылкой от сервера, связанного с адресом гиперссылки. Полученная страница, если таковая имеется, воспроизводится в ГИП, и сеанс просмотра продолжается. На устройство 108 может быть установлено приложение мониторинга, связанное с браузером, которое отслеживает и контролирует сеансы просмотра и выдает данные в журнал просмотра, связанный с сеансами. Анонимизированная информация, описывающая действия просмотра пользователя (включая, например посещенные страницы, время посещения, переданные запросы и т.д.), хранится в журнале просмотра.

Для поисковой службы в сети 102, такой как типичная поисковая служба, сервер поисковой системы 104 размещает веб-сайт, который предоставляет ГИП на дисплей устройства, которое осуществляет доступ к веб-сайту, дает возможность ввести в ГИП текст, касающийся Интернет-запроса, который будет выполнен через сервер поисковой системы 104. Например, когда запрос вводится через ГИП (например, "What is the capital city of France <CR>"), текст запроса анализируется сервером поисковой системы 104; инициируется поиск веб-страниц, которые отслеживаются сервером поисковой системы 104 для определения набора веб-страниц, которые совпадают с поиском; при этом список ранжированных веб-страниц отображается в графическом интерфейсе пользователя. Как только пользователь вызовет на устройстве один или несколько результатов поиска, веб-страницы с сервера 106, связанные с вызванной ссылкой, извлекаются и отображаются на устройстве 108.

Данные, относящиеся к истории сеансов просмотра, и поиски веб-системы, инициированные на устройствах 108/108b, могут быть отслежены и сохранены в устройстве 108/108b на его локальном устройстве(ах) хранения данных, на сервере 104 в его локальной базе данных 104b и/или в других местах (не показаны) в сети 102. История просмотра содержит записи данных, относящиеся к каждой веб-странице, посещенной во время сеанса просмотра, включая данные о том, когда начался сеанс, как начался сеанс, какие веб-сайты были посещены, когда были посещены веб-сайты, какова была продолжительность пребывания на каждом веб-сайте, как был получен доступ на каждый из веб-сайтов, как был завершен сеанс и когда был завершен сеанс и другие записываемые элементы. Различные элементы данных сеанса могут быть сохранены в различных местах. На устройствах 108 могут быть установлены и могут работать программные приложения, которые наблюдают и отслеживают сеансы просмотра в журнале просмотра. Данные истории просмотра для одного или нескольких устройств 108 могут быть сохранены в различных местах, например в базах данных поставщиков услуг Интернет связи (ISP), в файлах данных локального браузера на устройствах, так как браузеры и поисковые системы могут быть объединены в приложениях (например, в Chrome и Яндекс), в базах данных мобильных сетей, в данных, сохраняемых подключаемыми модулями браузера, работающего на устройстве 108, и в других приложениях, установленных в смартфонах и компьютерах. Различные устройства 108n, осуществляющие доступ к серверу поисковой системы 104, также могут локально и/или удаленно сохранять данные, относящиеся к их истории поиска. Данные могут быть получены и объединены из одного или нескольких различных мест и от одного или нескольких устройств 108, затем обработаны и проанализированы для определения тенденций в использовании пользователями ресурсов Интернет на устройствах 108, осуществляющих доступ к серверу поисковой системы 104. Данные истории просмотра могут быть запрошены и получены из различных локальных и удаленных источников посредством способов сбора данных, известных в данной области техники.

На фиг. 2 представлено схематическое отображение данных истории просмотра/поиска от одного или нескольких устройств 108, осуществляющих доступ из инструмента отображения, используемого в варианте реализации изобретения для создания и заполнения структур данных для сохранения истории и моделей просмотра веб-сайта. Истории 200(1), 200(2) … 200(n) представляют списки данных посещения веб-сайта для сеансов просмотра и/или сеансов поиска. Например, история 200(1) содержит записи 202(1) для устройства 108a о сеансе просмотра конкретного окна просмотра, имевшего место приблизительно 1 января приблизительно в 1:00-1:10 после полудня. Информация сеанса может включать один или несколько посещенных URL-адресов, время посещения и длительность пребывания на странице и способ посещения (например, вход по URL-адресу или по гиперссылке, нажатой на предыдущей странице).

В совокупности истории 200(1)…(n) могут быть отображены на графике 204, представляющем историю браузера для нескольких устройств 108, осуществляющих доступ к нескольким веб-страницам с нескольких серверов 108 в различные моменты времени. На графике 204 вершины 206(1), (2) … (n) представляют веб-страницы (соответствующие URL-адресам), а дуги 208(1), (2) .. (m), показанные как направленные стрелки, показывают переход от одного веб-сайта к другому одного устройства 108 в его истории просмотра, где основанием дуги является текущий веб-сайт, а верхняя часть дуги (со стрелкой) представляет полученный целевой веб-сайт, посещаемый после перехода (например, после активации гиперссылки на текущем веб-сайте для перехода на другой веб-сайт). Может существовать несколько дуг 208, соединяющих две вершины 206, где различные вершины отражают указанные переходы на веб-страницы, инициированные независимо различными устройствами 108. Как вариант, дуга 208, соединяющая две вершины 206, может отражать совокупные переходы на веб-страницы для всех устройств 108. График 204 показывает все истории просмотра 200(1) … (n) и не отражает в этом изображении одной конкретной истории просмотра. Согласно варианту реализации отображаются истории просмотра и генерируется набор данных, аналогичный графику 204, с дополнительным параметром времени (в отношении даты/времени каждого сеанса просмотра, используемого для построения графика), а затем применяет алгоритмы формирования данных для ранжирования веб-страниц посредством графика просмотра, такого как график 204. Эти данные могут быть получены от интернет-браузеров, установленных на устройствах 108, и/или собраны с серверов 106.

График 204 может быть представлен в формате таблицы посредством таблицы 210, содержащей строки и столбцы для каждой из вершин 206(1), (2) … (n), представляют веб-страницы, а ячейки 212 в записи (i, j) в таблице 210 предоставляют данные просмотра для перехода от вершины 206i к вершине 206j на графике 204. Записи в диагонали на записи (i, i) в таблице 210 предоставляют данные просмотра, оставшиеся в вершине i в сеансе просмотра. Например, записи могут включать параметр времени (например, отражающий время, когда произошел переход между веб-страницами для одного или нескольких устройств (полученный из истории просмотра от одного или нескольких источников), данные перехода (например, отражающие то, как были активированы переходы), данные о местоположении (например, отражающие расположение компьютеров, на которых были просмотрены веб-страницы) и другие данные (например, отражающие тип программного обеспечения, используемого для просмотра, и т.д.). Следует иметь в виду, что таблица 210 содержит данные, которые могут быть получены из данных истории просмотра или из других источников.

Один аспект варианта реализации изобретения предусматривает временной коэффициент (а именно коэффициент «свежести»), который используется для применения весового значения к веб-странице, которое присутствует в истории просмотра для веб-сеанса. Этот коэффициент свежести рассчитывается на основании записей в таблице 210 и используется как коэффициент при ранжировании значимости веб-страницы в истории просмотра.

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

Для сеанса просмотра (обозначаемого в данном документе как "S"), проведенного на устройстве 108, веб-страницы, посещенные в сеансе S, обозначаются как страницы p₁(S), p₂(S), … p_k(S)(S). В истории просмотра для каждого i∈{1, 2, …, k(S)-1} запись p_i(S) переходит в p_i+1(S): ("P_i(S)→p_i+1(S)"). Страницы p_i(S), P_i+1(S)являются смежными элементами сеанса S.

Для каждой страницы ("p") в истории просмотра s(p) является количеством сеансов, которые были инициированы на странице "p". Для каждой пары смежных элементов {p_i, p_i+1} сеанса I(p_i, p_i+1) является количеством сеансов, включающих эти пары смежных элементов.

График 204 алгебраически представлен как G=(V, Е), что можно рассматривать как другое алгебраическое представление данных, указанных в таблице 210. В этом отношении множество вершин V (представляющих вершины 206) включает все веб-страницы, определенные в истории просмотра, и включает дополнительную вершину x. Множество направленных дуг E (представляющих дуги 208) включает упорядоченные пары смежных элементов {p1, p2}. Множество Е также включает дополнительные дуги от последних страниц всех сеансов к вершине x.

Вероятность возврата σ(p) обозначается как вероятность выбора страницы p, когда начался новый сеанс просмотра. Она пропорциональна количеству сеансов с(p), начиная со страницы c. Соответственно, для одного варианта реализации изобретения вероятность возврата может быть установлена на ноль, так, чтобы σ(x)=0.

I(p, x) обозначает количество сеансов истории просмотра, который заканчивается на странице p, где p→x∈E. Вероятность перехода "ω" представляет вероятность активации гиперссылки на странице p₁ для перехода на p₂("p₁→p₂"), так, что:

Q(p) представляет расчетное время пребывания в истории просмотра на странице p. Ранжированное значение страницы p, обозначенное как ранг просмотра BR(p), выражается формулой:

BR(p)=Q(p)π(p) Уравнение 2

где

Следует иметь в виду, что уравнения 2 и 3 выполняются при p=x, а также если

Переменной, которая в варианте реализации изобретения вводится в анализ сеанса просмотра, является актуальность. Как правило, BR(p) может не отражать свежесть ссылки в истории просмотра. Таким образом, только ранжирование, основанное на BR(p), может представить результаты, в которых присутствует пользователь с ранжированием, где "старые" и "свежие" ссылки имеют вероятности, которые являются аналогичными, так как не учитывают временной компонент в своих вероятностях. Один из вариантов реализации изобретения включает показатель свежести истории просмотра, представляя функцию вероятности свежести просмотра (FBR). Более подробная информация по этому показателю свежести приводится ниже.

Для одного из вариантов реализации изобретения в рамках показателя свежести временные интервалы для сеанса просмотра используются для измерения «свежести» страницы в сеансе. Для сеанса просмотра с двумя моментами времени τ и T, где τ<T, временной интервал [τ, T] делится на К частей, так что для множества времен [t_i-1, t_i],

Время t(p) представляет время (например, дату), когда была создана страница p из V. Вершина x считается созданной в момент τ. Для временного интервала i∈{1, 2, … К} p∈V определяется как вершина (веб-страница), созданная до момента t_i.

В одном из вариантов реализации изобретения вычисляется оценка свежести на странице браузера, которая затем может быть использована в алгоритме ранжирования при анализе истории просмотра. Вариант реализации изобретения определяет функцию F («Свежесть») в момент времени t=i для начального значения , представляющего значение свежести страницы p и ее гиперссылки следующим образом:

где a⁰ и b⁰ - неотрицательные параметры, n_i(p)=1, если вершина p создается в i-м периоде, в противном случае n_i(p)=0; m_i(p) - количество посещений страницы за i-й период. В качестве первоначального расчета вариант реализации изобретения может установить . Чем выше значение в уравнении 5, тем "свежее" его оценка.

Иными словами, вариант реализации изобретения предусматривает значение свежести для веб-страницы p, ("f(p)"), которое основано на комбинации множества коэффициентов, каждый из которых может иметь весовое значение по отношению к другим коэффициентам. В одном из вариантов реализации изобретения f(p) для веб-страницы p включает элемент FBR(p) и запросо-зависимый элемент ("QD(p)") для веб-страницы. Элемент QD может быть получен из функции ранжирования документа, такой как ВМ25 (или "Okapi ВМ25"). Таким образом, f(p) может быть выражено как:

f_q(p)=λFBR(p)+(1-λ)QD(p,q) Уравнение 5b

где λ может иметь значения от 0 до 1. Таким образом, первый коэффициент для FBR(p) математически связан со вторым коэффициентом QD(p, q). Здесь математическая зависимость обратно пропорционально определяет два элемента по коэффициентам λ и (1-λ). В других вариантах реализации изобретения к элементам FBR и QD могут быть применены независимые коэффициенты.

Уравнение 5a позволяет рассчитать начальную величину . Уравнение 6, представленное ниже, определяет прирост (дельту) значения свежести, которое основано на распространении начального значения свежести по вершинам по направлению к исходящим дугам графика. В одном из вариантов реализации изобретения распространение включает использование времени, связанного с историей просмотра (в виде метки времени как значение свежести для веб-страниц в истории браузера) и арифметическое распределение компонента времени по веб-странице в истории просмотра в качестве части оценочного ранга для веб-страниц. Например, в истории просмотра переходу с веб-страницы X на веб-страницу Y 1 января 2013 г. будет предоставлен определенный оценочный ранг, основанный на свежести этого перехода относительно даты выполнения алгоритма ранжирования в соответствии с вариантом реализации изобретения. Также из истории просмотра переходу с веб-страницы X на веб-страницу Y на 1 февраля 2013 г. будет предоставлен другой оценочный ранг, основанный на свежести этого перехода относительно даты выполнения алгоритма ранжирования. Переход, выполненный 1 февраля 2013 г., может быть ранжирован выше (т.е. иметь более высокий удельный вес), чем переход, выполненный 1 января 2013 г., так как переход 1 февраля 2013 г. произошел позднее, чем переход 1 января 2013 г. В одном варианте реализации изобретения инкрементное значение свежести рассчитывается следующим образом:

где µ∈[0, 1]. W_i(p) является оценкой, присвоенной по "локальному" показателю свежести вершине p в i-й период. Этот локальный показатель определяется таким же образом, как начальные значения показателя :

В одном из вариантов реализации изобретения показатель свежести распространяется на исходящие гиперссылки со страницы, даже если среди них нет ни одной свежей гиперссылки. Таким образом, в расчете весовое значение страницы увеличивается по значению (например, увеличивается на 1), если она была создана до момента t_i. Результаты уравнения 7 демонстрируют влияние смежных элементов на показатель свежести страницы.

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

F_i(p)=βF_i-1(p)+ΔF_i(p) Уравнение 8

В качестве общей характеристики, если не происходит никаких действий, связанных с вершиной P (параметр β из (0, 1)), с течением времени показатель свежести уменьшается. Уменьшение может быть линейным, нелинейным или экспоненциальным. В одном из вариантов реализации изобретения применяется экспоненциальное уменьшение, так что:

F_i(p)=β_iΔF₀(p) Уравнение 9

если не было никаких действий по просмотру в период [τ, t_i]. Уравнения 8 и 9 представляют типичную формулу, которая может быть реализована в алгоритме для арифметически распределяемого компонента времени по всей веб-странице в истории просмотра как часть оценочного ранга для веб-страниц.

В примере применения анализа свежести в истории просмотра по одному из вариантов реализации изобретения предполагается, что для уравнения 7 все рассматриваемые вершины и дуги создаются до времени t_i.

Для этого примера показатель свежести задает для страницы p на графике G оценку свежести F_K(p). Значение количества сеансов, I, факторизуется с учетом вероятностной оценки свежести, так что I(p₁, p₂) заменяется на I(p₁, р₂)×F_K(p₂). Таким образом, вероятность свежести перехода ω_F(p1→p2) дуги p1→p2 представляется как:

где

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

Ниже приводится описание других функций по варианту реализации изобретения. Для показательного набора данных истории браузера f_q(p) представляет значение свежести страницы p для запроса q, для которого добавляется запросо-зависимый элемент (в уравнении 5б). Показательная история просмотра включает множество страниц , , … для каждого запроса q, которые упорядочены от наиболее актуальных ("самые последние") до наименее актуальных ("более старых") страниц. Другими словами, - это множество всех страниц с наивысшей оценкой, выбранных из меток k, страницы из множества имеют наиболее низкую оценку. Для любых двух страниц , ухудшение оценки h является функцией потерь. В одном из вариантов реализации изобретения h(i, j, f_q(p₂)-f_q(p₁)) представляет значение ухудшения, применяемое, если положение страницы p₁, соответствующее алгоритму ранжирования, выше, чем положение страницы р₂, но i<j. Функцией потерь в одном из вариантов реализации изобретения считается потеря с зазорами b_ij>0, где b_ij задается для каждой пары i, j и где 1≤i<j≤k, где h(i, j, x)=min{x+b_ij, 0}², т.е. где h(i, j, x)=0 if x+b_ij>0, в противном случае h(i, j, x)=(x+b_ij)². Вектор ω представляет собой вектор параметров значений истории браузера. В одном из вариантов реализации изобретения значение свежести в

можно свести к минимуму посредством основанного на градиенте оптимизационного анализа, такого как градиентный спуск. В рамках оптимизационного анализа градиент может быть рассчитан для π_f(р) вместо F(ω), так как F(ω) представляет собой сумму функций h(i, j, x) и так как функция h состоит из h(x) и f_p(x). Таким образом:

и таким образом:

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

В частности, в одном из вариантов реализации изобретения применяется производная функции для стационарного распределения марковского процесса истории браузера, когда его вероятности переходов являются функциями стационарного распределения другого марковского процесса. Частные производные ∂π_Fresh/∂α, ∂π_F/∂β как решения системы линейных уравнений могут быть вычислены в результате решения уравнений:

Решение для производной ω/∂β(q→р) может быть определено путем вычисления ∂F_k/∂β (р) из следующего уравнения:

Таким образом, в одном из вариантов реализации изобретения может использоваться система линейных уравнений, имеющих решения для ∂π_F/∂µ, ∂π_F/∂а₀, ∂π_F/∂a₁ (производные ∂π_F/∂b₀, ∂π_F/∂b₁ являются решениями тех же уравнений).

Первые уравнения системы линейных уравнений могут быть такими же, как уравнение 15. После выбора параметра для β остальные значения, подлежащие определению: ∂ΔF_i/∂µ, ∂ΔF_i,/∂а₀ и ∂ΔF_i/∂a₁. В одном из вариантов реализации изобретения эти значения определяются следующим образом:

где

Исходя из уравнений 17 и 18 значения для различных параметров (например, α, а⁰ и а¹) могут быть получены за выбранные интервалы времени. Таким образом, в одном из вариантов реализации изобретения значения параметров τ, Т, K определяются и заносятся в уравнения 17-18 для получения значений параметров. Значения параметров τ, Т, K могут быть выбраны из относительно небольшого количества значений. Например, в одном из вариантов реализации изобретения в качестве периода времени [τ, Т] может использован период 1 неделя, а параметр К может быть выбран таким образом, что продолжительность одного периода [t_i-1, t_i] выбирается из различных значений времени, таких как: давность веб-страницы составляет 1 день, давность 6 часов, давность 3 часа и давность 1 час. Более поздние, недавние (т.е. "более свежие") страницы, содержащиеся в истории просмотра, могут быть оценены (ранжированы) выше, чем более старые страницы. Таким образом, временные данные, включенные в данные истории просмотра, выделяют те результаты в истории, которые являются более поздними, чем данные просмотра, которые в истории более старые. Могут быть использованы и другие периоды времени и интервалы. Следует понимать, что в конкретном варианте реализации изобретения могут использоваться различные параметры для выявления более свежих страниц среди более старых страниц. В одном из вариантов реализации изобретения может использоваться относительный порог (например, более свежими страницами являются страницы, просмотренные за последний час, день, неделю, месяц и т.д. от текущей даты или события) или параметры для выявления более свежих страниц среди более старых страниц. В одном из вариантов реализации изобретения может использоваться абсолютный порог (например, более свежими страницами являются страницы, просмотренные до 1 января 2013 года или другой установленной даты или времени или события).

Как только определены значения параметров из уравнений 17 и 18, определяются значения параметров, перечисленные в таблице А. Таким образом, с помощью уравнения 10 посредством всех рассчитанных значений можно вычислить хронологический ранг для веб-страницы, получая при этом оценку для веб-страницы. Этот способ может быть повторен для получения N оценок N веб-страниц, и веб-страницы могут быть ранжированы в соответствии с такой оценкой. Таким образом, когда устройство 108 осуществляет доступ к серверу поисковой системы 104 и когда устройство 108 отправляет поисковый запрос на сервер 104, сервер 104 может анализировать данные, относящиеся к истории просмотра, к которым осуществляется доступ, выбрать соответствующие значения для временных интервалов, рассчитать параметры FBR уравнений (например, уравнений 17 и 18), рассчитать время, основанное на оценках истории просмотра для веб-страниц, ранг оцененных веб-страниц и отправить результаты поиска на устройство 108 для выдачи на его дисплей ранжированного списка веб-страниц как результатов поиска по поисковому запросу.

Далее приводится подробная информация по устройствам, которые совокупно осуществляют все функции вариантов реализации изобретения, описанных в данном документе.

Как показано на фиг. 3, устройство 108 является вычислительным устройством, которое подключается к сети 102. Устройство 108 собрано на базе процессора, имеющего типичные компьютерные элементы, включающие дисплей 300, процессор 302, запоминающее устройство (память) 304, жесткий диск вспомогательного запоминающего устройства (не показан) и модуль связи 306 (что составляет элементы необходимого оборудования, программного обеспечения и микропрограммного обеспечения для обеспечения возможности подключения устройства 108 к внешним сетям, таким как сеть 102). Приложения хранятся в памяти 304, предоставляя инструкции, выполняемые на процессоре 302, позволяющие процессору 302 управлять характеристиками и функциями устройства 108, получать входные данные и выдавать выходные данные. Браузер 308 генерирует набор графических интерфейсов пользователя (ГИП) на дисплей 300 и позволяет вводить данные в ГИП (например, с клавиатуры, мыши, сенсорной панели, внешних устройств и т.д.). Следует отметить, что устройство 108 может быть «тонким» или «толстым» клиентом сети 102. Статистика может отслеживаться и сохраняться на устройстве 102 в памяти 304. Например, может быть сохранен файл данных 310, содержащий историю просмотра, сгенерированную браузером 308. История просмотра может включать все или некоторые из данных, описанных в данном документе для более ранних историй просмотра.

Как показано на фиг. 4, сервер 104 находится в сети 102, а также является вычислительным устройством. Сервер 104 может быть отдельным сервером или включать несколько серверов. Сервер 104 является устройством на базе процессора, включающего процессор 400, запоминающее устройство 402, доступ к базе данных вспомогательного запоминающего устройства 104b и модуль связи 404 (что составляет элементы необходимого оборудования, программного обеспечения и микропрограммного обеспечения для обеспечения возможности подключения сервера 104 к внешним устройствам и сетям, таким как устройство 108 и сеть 102). Приложения хранятся в памяти 402, предоставляя инструкции, выполняемые на процессоре 400, позволяющие процессору 400 управлять характеристиками и функциями консольного сервера 104. Приложение поисковой системы 406 хранится в памяти 402 и предоставляет инструкции процессору 400 для анализа данных истории просмотра, ранжирования веб-страниц и генерирования ранжированных результатов в ответ на запросы. Приложение поисковой системы 406 может включать алгоритмы, которые воплощают любое из уравнений определения ранга страницы, представленных в данном документе.

Как показано на фиг. 5, процесс 500 является блок-схемой типичных процессов, выполняемых приложением поисковой системы 406 на сервере 104 через процессор 400. После того как поисковая система 406 инициирует стартовый процесс 502, в какой-то момент сервер 104 получает сигнал, что ему бы отправлен запрос (например, от устройства 108). В этот момент процесс 504 получает запрос и инициирует анализ ранга свежести просмотра, как описано в этом документе. В рамках процесса 504 извлекаются данные истории просмотра. Данные истории просмотра могут быть частично доступны локально (например, из базы данных 104a или памяти 402), и/или они могут быть доступны удаленно (например, от устройства 108). После извлечения истории просмотра в процессе 506 определяются различные параметры для анализа ранга свежести просмотра ("РСП"). В одном из вариантов реализации изобретения временные параметры (например, τ, Т, K) выбирают из заданных диапазонов/значений. Когда параметры выбраны, один или несколько параметров из уравнения РСП (например, из уравнений 17 и 18) могут быть вычислены для данной истории браузера в процессе 508. Это действие может включать применение производной функции для стационарного распределения марковского процесса истории браузера, когда его вероятности переходов являются функциями стационарного распределения другого марковского процесса. Одно или несколько из этих значений могут быть предварительно рассчитаны и просто получены приложением. Далее, в процессе 510, оценка РСП вычисляется посредством соответствующего уравнения РСП (например, уравнения 10) для каждой веб-страницы в истории. В процессе 512 все веб-страницы ранжируются, по меньшей мере частично, по оценке РСП и ранжированные результаты могут быть отправлены на устройство в сети, например на устройство 108, которое инициировало запрос. Приемное устройство (например, устройство 108) может получить доступ к результатам и ранжированному списку веб-страниц, сгенерированному на его дисплее. Далее, в процессе 514, выполняется проверка того, не обновлялись ли одна или несколько историй браузера и/или не выполнялось ли другое условие запуска (например, завершение заданного периода времени с момента последнего выполнения ранжирования, такого как день, неделя или месяц и т.д., наличие события изменения в среде просмотра, такого, как ввод или потеря заданного количества историй браузера или веб-страниц и т.д.). Если это так, процесс 500 осуществляет возврат к процессу 506, но вместо этого в другом варианте реализации изобретения он может осуществить возврат к другому процессу (например, процессу 502, 504, 508, 510 и т.д.). Как вариант или дополнительно, процесс 500 может инициировать промежуточный процесс (не показан) до осуществления возврата (к процессу 506) или может породить другой процесс.

Следует понимать, что в других вариантах реализации изобретения порядок процессов в процессе 500 может быть перестроен и могут быть предусмотрены дополнительные процессы. Процесс 500 показан как выполняющийся на сервере 104, но его реализация может быть распределена между многими серверами/устройствами. Процесс 500 может частично или полностью выполняться на устройстве 108.

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

Коэффициент релевантности был отмечен посредством классифицирующей метки, например идеально, отлично, хорошо, удовлетворительно, плохо. Данные просмотра были разделены на две части. В первой части, содержащей 75% набора данных, параметры были сформированы, как отмечено выше, а по второй части были протестированы алгоритмы, описанные в этом документе. Параметры для теста для одного из вариантов реализации изобретения были определены путем максимизации функции потерь так, как было описано выше. Параметры для таблицы А были определены посредством максимизации показателя нормализованного дисконтированного прироста (NDCG) с получением следующих значений:

K=24, а≈5.2, b≈1.0, а≈6.9, b≈1.1, µ=0.2, α=0.18, β=0.9.

Значение K было выбрано из множества {7, 28, 56, 168}. В этих случаях длина периодов [t₁₊₁, t_i] равна 1 дню, 6 часам, 3 часам и 1 часу соответственно. Таблица В демонстрирует результаты выполнения ранжирования по показателям NDCG@5 и NDCG@10 по алгоритмам ранжирования в соответствии с вариантом реализации изобретения.

Следует понимать, что варианты реализации изобретения, связанные с клиентскими устройствами, серверными устройствами и системами, могут быть реализованы как комбинация электронных модулей, оборудования, микропрограммного обеспечения и программного обеспечения. Оборудование и программное обеспечение могут быть реализованы в виде последовательности процессов, приложений и/или модулей, которые обеспечивают функциональность, описанную в этом документе, обычно предоставляя инструкции для выполнения на соответствующем процессоре. Инструкции могут быть сохранены в запоминающем устройстве на одном из или на обоих: клиенте или серверном устройстве, доступных процессору. Как правило, запоминающее устройство локально расположено в том же устройстве (или рядом с тем же устройством), где и процессор. Модули, приложения, алгоритмы и процессы, описанные в данном документе, могут быть выполнены в другом порядке(ах) и параллельно. Могут быть использованы обработчики прерываний. Данные, приложения, процессы, программы, программное обеспечение и инструкции могут храниться в описанных энергозависимых и энергонезависимых устройствах и могут предоставляться на другом материальном носителе, таком как USB-накопители, компьютерные диски, CD, DVD или другие носители, и могут обновляться модулями, приложениями, оборудованием, микропрограммным обеспечением и/или программным обеспечением. Данные, приложения, процессы, программы, программное обеспечение и инструкции могут быть отправлены от одного устройства к другому с помощью передачи данных.

При использовании в данном документе выражение "и/или" предполагает указание включающего «или». То есть "X и/или Y" означает X или Y или то и другое.

В данной публикации, где пороговое значение или измеренное значение предполагает их приблизительную величину (например, когда порог определяется со словом «приблизительно»), следует понимать, что для этого значения действует диапазон величин. Например, для порога, указанного как приблизительное значение, может быть использован диапазон примерно на 25% больше и на 25% меньше, чем установленное значение. Пороговые значения, значения, измерения и размеры функций являются демонстрацией вариантов реализации изобретения и не являются ограничивающими, если не указано иное. Кроме того, в качестве примера "достаточным" соответствием заданному порогу может быть значение, которое находится в пределах используемого порога, принимая во внимание, что приблизительное значение применимо к порогу, и подразумевая диапазон значений (выше и ниже), которые могут быть применяться в отношении такого порога.

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

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