Определение намерения пользователя

Определение намерения пользователя

Иллюстрации

Показать все

Реферат

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

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

Предшествующий уровень техники

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

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

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

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

Известные средства поиска, чтобы смягчить упомянутые выше недостатки, могут также использовать способы кластеризации. Например, чтобы способствовать получению более релевантных результатов по запросу на поиск, сайты могут быть кластеризованы. С возвращенным результатом может быть ассоциирована ссылка, названная "больше подобных этому" (“more like this”), и выбор ссылки может способствовать дополнительной кластеризации и/или отображению документов внутри кластера, ассоциированного со ссылкой “больше подобных этому”. Однако выявленный через запрос релевантный документ (и, соответственно, релевантный кластер) может быть возвращен пользователю в позиции, которая указывает, что документ не строго релевантен запросу. Соответственно, пользователь может быть вынужден прочитывать страницы документов для выявления информации, которую был намерен найти. Кроме того, постоянная кластеризация документов является затратной в вычислительном отношении.

Другая возможная система, используемая известными средствами поиска, когда введенный запрос пользователя не возвращает никаких документов, обеспечивает пользователя запросом. Например, пользователю может потребоваться найти информацию, связанную с ранними работами Моцарта. Как является обычным, пользователь может иметь намерение ввести недоопределенный запрос "классическая музыка". Однако, если пользователь ошибочно вводит запрос "клссическая музыка", то средство поиска может определить, что по запросу не возвращены никакие документы (из-за опечатки в запросе). После этого средство поиска может выдать подсказку пользователю запросом, который средство поиска считает, по существу, подобным введенному запросу. Например, средство поиска может осуществить подсказку пользователю, запрашивая "Вы подразумевали 'классическая музыка'?". Если пользователь отвечает положительно, то может быть выполнен правильный запрос и могут быть получены результаты. Хотя такая система полезна в отношении исправления опечаток и орфографических ошибок, она не предоставляет результаты, тесно связанные с ранними работами Моцарта (истинным намерением пользователя). Скорее пользователь будет завален существенным объемом информации, которая хотя и связана с классической музыкой, не связана с ранними работами Моцарта. Например, пользователю может потребоваться просмотреть сотни записей до выявления документа, содержащего требуемую информацию.

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

Сущность изобретения

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

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

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

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

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

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

Перечень фигур чертежей

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

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

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

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

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

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

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

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

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

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

Фиг.11 - иллюстративная компоновка наборов результатов, согласно аспекту настоящего изобретения.

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

Фиг.13 - иллюстрация одной возможной реализации настоящего изобретения.

Фиг.14 - иллюстрация другой возможной реализации настоящего изобретения.

Фиг.15 - иллюстрация еще одной возможной реализации настоящего изобретения.

Фиг.16 - иллюстрация еще одной возможной реализации настоящего изобретения.

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

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

Подробное описание предпочтительных вариантов осуществления

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

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

Согласно фиг.1 иллюстрируется система 100, обеспечивающая определение намерения пользователя при заданном запросе пользователя на поиск. Система 100 содержит средство 102 поиска, которое принимает запрос и используется для поиска, в соответствии с таким запросом, по объектам внутри информационного хранилища 104. Средство 102 поиска может применять любой соответствующий алгоритм(ы) поиска, чтобы выявить, ранжировать и извлечь объекты, которые постоянно находятся внутри информационного хранилища 104. Кроме того, средство 102 поиска может использоваться для любого соответствующего поиска. Например, средство 102 поиска может выполнять текстовый поиск, что является обычным при поиске через Интернет. Однако средство 102 поиска может применяться также, чтобы использовать цветовые схемы для поиска коллекции изображений, чтобы использовать звуковые байты для поиска конкретных звуков, или любых других соответствующих объектов, которые требуется найти пользователю. Кроме того, запрос, принимаемый средством 102 поиска, не обязательно должен быть строкой текста. Например, запросом может быть звук или последовательность звуков, форма, цветное растровое изображение и т.д.

По приеме запроса средство 102 поиска осуществляет поиск по совокупности объектов в информационном хранилище 104 и извлекает объекты, соответствующие запросу. Согласно одному аспекту настоящего изобретения информационное хранилище 104 может постоянно находиться на сервере и содержать несколько web-страниц или других документов, которые могут постоянно находиться в сети Интернет и/или интранет. Кроме того, информационное хранилище 104 может постоянно находиться на накопителе на жестких дисках и/или в памяти персонального компьютера (например, клиента). Должно быть понятно, что информационное хранилище 104 и объекты внутри такого информационного хранилища 104 не ограничиваются web-страницами, которые постоянно находятся в Интернет и/или интранет. Информационное хранилище 104 (или отдельное информационное хранилище, средство 102 поиска, …) может соотносить объекты внутри информационного хранилища с запросами, которые использовались ранее для извлечения таких объектов. Например, объект 1 внутри информационного хранилища 104 был ранее выявлен через средство 102 поиска в связи с запросами Q1, Q2 и Q4. Аналогично, объект 2 внутри информационного хранилища 104 был ранее выявлен средством 102 поиска в связи с запросами Q2, Q5 и Q8. Часто запрос, принятый средством поиска, будет недоопределенным, что, следовательно, приводит к возврату существенного количества объектов, не связанных с объектами, которые намеревался найти пользователь. Настоящее изобретение разбивает набор результатов, соответствующий принятому запросу, используя другие запросы, использованные ранее для выявления объектов внутри информационного хранилища 104.

Более конкретно, для заданного конкретного запроса средство 102 поиска извлекает несколько объектов (первоначальный возвращаемый набор), которые находятся внутри информационного хранилища 104, причем эти объекты ассоциированы с запросами, использованными ранее для выявления таких объектов. Внутри первоначального возвращаемого набора имеется по меньшей мере один объект, который предпочтительно рассматривается пользователем, который ввел запрос в средство 102 поиска (например, пользователь намеревался выявить такой объект, но не сформировал достаточно определенный запрос). Средство 102 поиска связано со средством 106 вычисления взаимосвязи, которое разбивает первоначальный возвращаемый набор на несколько возвращаемых наборов на основе возвращаемых наборов для запросов, ассоциированных с объектами в информационном хранилище 104. Средство 106 вычисления взаимосвязи, по существу, просматривает каждый запрос (возвращаемый набор, ассоциированный с каждым запросом), который ассоциирован с объектами внутри первоначального возвращаемого набора, и определяет уровень взаимосвязи между первоначальным запросом и запросами, использованными ранее для выявления объектов внутри первоначально возвращаемого набора. Затем средство 106 вычисления взаимосвязи может определить несколько запросов, которые пользователь может посчитать полезными для выявления одного или большего количества объектов. Запросы, сильно связанные с первоначальным возвращаемым набором и к тому же выводящие другие объекты, могут быть возвращены пользователю через устройство 108 отображения. Например, запрос, который возвращает, по существу, идентичные объекты в пределах первой совокупности объектов, в соответствии с ранжированием, заданным средством 102 поиска, является сильно связанным, но не выводит новые результаты. В более конкретном примере, первоначальным запросом может быть "ужение нахлыстом". Связанным запросом должен быть "нахлыст & ужение", но, например, по существу, подобные объекты должны быть возвращены на первой странице результатов. Соответственно, средство 106 вычисления взаимосвязи не должно возвращать такой запрос пользователю, так как запрос выведет, по существу, аналогичные результаты. Аналогично, пользователю не должен возвращаться запрос, который приводит к возврату, по большей части, не связанных объектов, так как средство 106 вычисления взаимосвязи должно определить, что такой запрос, по большей части, не является связанным. Для конкретного примера, объект, ориентированный на танцы, может включать в себя малую долю, связанную с ужением нахлыстом. Однако большинство запросов, связанных с этим объектом, скорее должны возвратить многочисленные объекты, связанные с танцами, чем объекты, связанные с ужением нахлыстом. Соответственно, средство 106 вычисления взаимосвязи может определять уровень связанности между первоначальным запросом и запросами, ассоциированными с объектами, возвращенными посредством первоначального запроса, и возвращать пользователю запросы, которые ассоциированы со связанными объектами, а также с новыми объектами.

В одном конкретном примере, Q может быть набором запросов, которые использовались средством 102 поиска ранее в связи с поиском объектов в информационном хранилище 104 или других подобных информационных хранилищах, а q может быть запросом, который введен в средство 102 поиска пользователем. D может быть набором объектов, выявленных внутри информационного хранилища 104, а d может быть одним конкретным объектом, который пользователь намерен найти посредством запроса q. R может быть определено как бинарное отношение на QхD, где qRd тогда и только тогда, когда d находится в возвращаемом наборе для запроса q. Соответственно, для заданного запроса q средство 106 вычисления взаимосвязи может выявить все запросы q', такие что (∃d ∈ D)(qRd ∧ q'Rd). Более конкретно, средство 106 вычисления взаимосвязи определяет возвращаемый набор (R^-1 o R)[q]. Однако должно быть понято, что согласно настоящему изобретению, могут быть выявлены и отображены запросы вне этого набора результатов. Например, в связи с настоящим изобретением может быть использован другой показатель связанности запросов. В большинстве случаев для недоопределенного запроса возвращаемый набор (R^-1 o R)[q] является очень большим (например, недоопределенный запрос может иметь тысячи связанных запросов). Так как представление пользователю тысяч запросов является нецелесообразным, средство 106 вычисления взаимосвязи может применять различные алгоритмы для измерения связанности между первоначальным запросом q и запросами внутри возвращаемого набора (R^-1 o R)[q]. Согласно одному аспекту настоящего изобретения, средство 106 вычисления взаимосвязи может применить алгоритм

,

и после этого отсортировать набор связанных запросов в соответствии с ║q, q'║ и возвратить пользователю некоторое количество запросов, находящихся на самом верху.

Согласно одному аспекту настоящего изобретения в связи с вычислением показателя расстояния ║q, q'║ могут рассматриваться относительные ранжирования. Например, в связи с вычислением показателя расстояния может быть принят во внимание тот момент, что объекта d возвращается для двух запросов q и q'. Более конкретно, показатель расстояния может вычисляться иным образом, когда объект d является первым результатом, возвращенным для каждого из двух запросов q и q', по сравнению с тем, когда объект d является 100-ым результатом, возвращенным для одного или большего количества из двух запросов q и q'. Например, показатель расстояния может быть вычислен следующим образом:

где w является весовой функцией для объекта, независимой от запроса, (например, Рангом_Страницы (PageRank) объекта). Пока соответствующий w диапазон является положительным функция, определенная выше, является показателем расстояния. Однако должно быть понято, что рассмотрение относительных ранжирований не является необходимым для эффективного функционирования одного или большего количества аспектов настоящего изобретения.

Однако, обычно, набор связанных запросов, отсортированный в соответствии с показателем расстояния ║q, q'║, будет слишком подобным первоначальному запросу, чтобы быть выгодным для пользователя (например, запросы будут возвращать объекты, по существу, подобные объектам, возвращаемым посредством первоначального запроса). Соответственно, для нахождения запросов, которые возвращают связанные объекты, но не возвращают, по существу, подобные объекты, по сравнению с набором результатов первоначального запроса, может быть применена модифицированная схема максимальной граничной релевантности (MMR) или другая соответствующая схема релевантности. Модифицированная схема MMR может применяться средством 106 вычисления взаимосвязи для возвращения пользователю запросов с наборами результатов, которые являются и релевантными, и новыми. Более конкретно, модифицированная схема MMR может быть использована средством 106 вычисления взаимосвязи для представления пользователю запросов q', которые имеют наборы результатов, связанные с набором результатов первоначального запроса q, но новые относительно наборов результатов первоначального запроса и других запросов, которые были возвращены ранее. Согласно одному аспекту настоящего изобретения средство 106 вычисления взаимосвязи может использовать для определения измерения взаимосвязи запросов внутри набора запросов Q следующий алгоритм:

arg min[λ║q,q'║-(1-λ) min║q',q”║],

q'

q”

где λ является коэффициентом интерполяции, установленным априорно, q является первоначальным запросом, q' является запросом, связанным с первоначальным запросом q, но отличным от других уже возвращенных запросами q". Запросы q' выводятся из расширений невозвращенных запросов, а запросы q" выводятся из набора, возвращенного ранее. После этого запросы могут выбираться итерационно, в соответствии с измерением взаимосвязи. Уравнение, приведенное выше, основано на схеме MMR, которая была введена исходно для ранжирования документов при установке чисто информационного извлечения, в которой возвращенные документы должны были быть одновременно релевантными и новыми. В известной схеме применяются показатель подобия s_q, иллюстрирующий подобия между документами и запросами, а также показатель подобия s_d, иллюстрирующий подобие между документами и другими документами. После этого документы выбираются итерационно в соответствии со следующим взвешиванием:

arg maxλs_q (q,d)-[1-λ] max s_d(d, d'),

d∈D

d'∈D'

где D является набором объектов, еще не возвращенных, а D' является набором объектов, уже возвращенных. Как и в модифицированной схеме MMR, λ является коэффициентом интерполяции, который был выбран ранее. При этом алгоритме выбирается объект d, который является максимально подобным запросу q и, одновременно, максимально отличным от других документов, d', возвращенных ранее. Например, когда λ = 1, ранжирование осуществляется просто в соответствии с подобием между объектом d и запросом q. Когда λ = 0, алгоритм осуществляет попытку формировать максимально отличающиеся результаты, независимо от запроса q. Модифицированная схема MMR была получена благодаря пониманию авторами настоящего изобретения того, что сформированные ранее запросы могут содействовать пользователю в выявлении объекта, который пользователь намеревался найти.

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

Хотя настоящее изобретение может применяться в связи с содействием пользователю, который использует недоопределенный запрос, должно быть понятно, что настоящее изобретение может также применяться для содействия одному или большему количеству пользователей, которые передают в средство 102 поиска любой подходящий запрос, представляющий для них интерес. Кроме того, настоящее изобретение может использоваться для содействия пользователю в случайном выявлении информации. Например, пользователь может предоставить общий запрос, и настоящее изобретение может возвратить информацию, косвенно связанную с таким запросом. Более конкретно, пользователь может ввести в средство 102 поиска запрос "медовый месяц", и в соответствии с таким запросом может быть выявлен возвращаемый набор объектов внутри информационного хранилища 106. После этого может быть использовано средство 106 вычисления взаимосвязи для выявления запросов, которые, не обязательно являются более определенными, чем первоначальный запрос “медовый месяц”, но, тем не менее, являются связанными (например, связанными случайно). Например, запросом, возвращенным пользователю на основе первоначально введенного запроса "медовый месяц", может быть запрос "заявления на паспорт". Это возможно при требовании меньшего перекрытия между возвращаемыми наборами первоначального запроса и рассматриваемых запросов. Например, возвращаемые наборы для запроса "медовый месяц" будут иметь меньшее перекрытие с возвращаемым набором для запроса "заявления на паспорт" по сравнению с возвращаемым набором для запроса "наборы программ для медового месяца". Большее перекрытие между возвращаемыми наборами для запросов приводит к возврату более подобных и менее случайных запросов, меньшее перекрытие между возвращаемыми наборами для запросов приводит к возврату более случайных и менее подобных запросов. Согласно одному аспекту настоящего изобретения может быть обеспечен компонент (не изображен), который обеспечивает возможность выбора пользователем уровня перекрытия между возвращаемыми наборами. Кроме того, уровень перекрытия между возвращаемыми наборами может определяться автоматически по меньшей мере частично на основе одного или большего количества из идентификатора пользователя, состояния пользователя и контекста пользователя.

Согласно фиг.2 иллюстрируется система 200, обеспечивающая поиск по совокупности объектов. Система 200 использует первоначальный запрос, который предоставляется пользователем, и выявляет запросы, которые были сформированы ранее (например, разными пользователями), связанные с первоначальным запросом, но не возвращают, по существу, подобные объекты, такие как возвращаются при использовании первоначального запроса. Средство 202 поиска принимает первоначальный запрос и использует такой запрос для поиска по совокупности документов в информационном хранилище 204. Средство 202 поиска, в связи с выявлением и возвратом объектов внутри информационного хранилища 204, может применять различные алгоритмы. Например, средство поиска 204 может выполнять текстовый поиск (например, возвращать объекты на основе мета-тегов, текста внутри объектов, …), поиск по меньшей мере частично на основе кластеризации и т.д. Информационное хранилище 204 содержит совокупность объектов, которые могут быть извлечены через средство поиска, и каждый объект ассоциирован с одним или большим количеством запросов, ранее использованных средством 202 поиска для выявления таких объектов. Например, средство 202 поиска извлекало объект 1 ранее, использовав запросы Q1, Q2 и Q4. Хотя запросы, ассоциированные с объектами, изображены находящимися внутри информационного хранилища 204, должно быть понятно, что такие запросы могут постоянно находиться в другом местоположении. Например, средство 202 поиска может само хранить список запросов и имен (например, указателей URL) объектов, извлеченных посредством запросов. Аналогично, средство 202 поиска может поддерживать список объектов, извлеченных ранее, а также запросов, использованных для извлечения таких объектов. Кроме того, списки объектов и запросов могут быть сжаты посредством хеширования или другого подобного способа.

По приеме запроса средство 202 поиска выявляет совокупности объектов внутри информационного хранилища 204 согласно такому запросу. Средство 202 поиска может включать в себя компонент 206 ранжирования, который используется для ранжирования возвращенных объектов согласно их релевантности в отношении запроса. Однако в случаях, в которых запрос является недоопределенным, пользователю могут быть возвращены и ранжированы компонентом 206 ранжирования тысячи объектов, которые были посчитаны релевантными для такого запроса. Кроме того, так как могут быть выявлены и возвращены тысячи объектов, также имеется существенное количество запросов, которые были использованы ранее для выявления таких объектов. Однако просмотр каждого запроса для каждого возвращенного объекта для определения связанности с первоначальным запросом может быть затратным в вычислительном отношении. Для уменьшения количества объектов, которые должны рассматриваться, может быть обеспечен компонент 208 фильтрации. Например, компонент фильтрации может фильтров