ОПРЕДЕЛЕНИЕ НАМЕРЕНИЯ ПОЛЬЗОВАТЕЛЯ Российский патент 2010 года по МПК G06F1/00 

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

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

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

Развитие компьютеров и сетевых технологий от дорогостоящих малоэффективных систем обработки данных до дешевых систем решения задач и развлекательных систем с высокоэффективной связью обеспечило рентабельное и времясберегающее средство для облегчения бремени выполнения каждодневных задач, таких как переписка, оплата счетов, покупка товаров, составление сметы и сбор информации. Например, вычислительная система, соединенная с Интернетом посредством проводной или беспроводной технологии, может по нажатию пользователем клавиши обеспечить его каналом для почти мгновенного доступа к необычайному многообразию информации из архива 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 фильтрации. Например, компонент фильтрации может фильтровать объекты, которые не ранжированы, как один из двадцати верхних объектов, компонентом ранжирования 206. Кроме того, компонент 208 фильтрации может использоваться для удаления дублированных запросов, соответствующих возвращенным объектам. Например, если средство 202 поиска возвращает объект 1, который ассоциирован с предыдущими запросами Q1, Q2 и Q4, а также объект 3, который ассоциирован с запросами Q1, Q2 и Q8, то компонент 208 фильтрации может гарантировать, что запросы Q1 и Q2 не будут рассматриваться дважды (или более, чем дважды).

Средство 202 поиска также включает в себя средство 210 вычисления взаимосвязи, которое определяет уровень связанности между первоначальным запросом и запросами, которые использовались средством 202 поиска ранее. Например, если первоначальный запрос возвращает объект 1 из информационного хранилища 204, то средство 210 вычисления взаимосвязи может определить уровень связанности между первоначальным запросом и запросом Q1, запросом Q2 и запросом Q3. Средство 210 вычисления взаимосвязи может определять также уровень связанности между другими запросами, которые использовались средством 202 поиска ранее (например, запросами Q1, Q2, …). Например, средство 210 вычисления взаимосвязи может определить уровень связанности между запросами Q1 и Q2. Это полезно, когда запросы Q1 и Q2 возвращают, по существу, подобные документы, соответственно, в отношении пользователя не выгодно отображать оба запроса Q1 и Q2. Согласно одному аспекту настоящего изобретения средство 210 вычисления взаимосвязи может определять показатель расстояния между первоначальным запросом и запросами, использованными ранее, и вычислитель взаимосвязи может использовать показатель расстояния в связи с модифицированным алгоритмом MMR для определения того, какие из предыдущих запросов являются связанными с первоначальным запросом и также ассоциированы с возвращаемым набором, содержащим новые объекты. Более конкретно, обеспечение запроса, связанного с возвращаемым набором, который, по существу, подобен возвращаемому набору, ассоциированному с первоначальным запросом, не будет содействовать пользователю в выявлении объекта, соответствующего намерению такого пользователя. Скорее, пользователю будет предоставлена дублированная информация, соответственно, препятствуя осуществлению пользователем поиска.

После выявления средством 210 вычисления взаимосвязи совокупности запросов, связанных с первоначальным запросом, но ассоциированных с новым возвращаемым набором, компонент 208 фильтрации может уменьшить количество объектов, ассоциированных с запросами. Например, компонент 208 фильтрации может использоваться для обеспечения возможности отображения только высокоранжированных объектов внутри возвращаемого набора, ассоциированного с запросом (например, будет возвращено пять наиболее высокоранжированных объектов). Кроме того, компонент 208 фильтрации может использоваться также для удаления объектов из возвращаемого набора, ассоциированного с возвращенным запросом, причем объекты находятся также внутри возвращаемого набора первоначального запроса или другого возвращенного запроса. Например, возвращаемый набор для первоначального запроса может содержать объект 1, и запрос Q1 может быть посчитан сильно связанным с первоначальным запросом. Так как запрос Q1 использовался ранее для выявления объекта объект 1, то объект 1 должен постоянно находиться в возвращаемом наборе для первоначального запроса, а также в возвращаемом наборе для запроса Q1. Компонент 208 фильтрации может использоваться для удаления объекта объект 1 из набора результатов, ассоциированного с Q1, вследствие этого гарантируя, что пользователь не будет принимать дублированные объекты. Кроме того, компонент 208 фильтрации может использоваться для удаления запросов, которые лексически подобны первоначальному запросу. Например, могут отбрасываться запросы, слова в которых являются просто перестановками слов первоначального запроса. Эти лексически подобные запросы могут быть высоко ранжированы средством 210 вычисления взаимосвязи, но возвращаемые наборы, ассоциированные с первоначальным запросом и лексически подобными запросами, по существу, подобны, следовательно, не обеспечивают пользователя новой информацией.

Согласно другому аспекту настоящего изобретения компонент 208 фильтрации может удалять из рассмотрения запросы, которые оказываются путями к конкретному объекту. Например, в контексте Интернета, могут быть удалены из рассмотрения все запросы, которые содержат строки "www.", ".com", ".net", ".org" и т.д., так как может предполагаться, что такие запросы скорее ошибочно были помещены в окно запроса средства поиска вместо адресной строки браузера. Возвращаемые наборы, ассоциированные с этими строками, в основном, не соответствуют намерению пользователя, и представление URL, пути или другого подобного идентифицирующего индекса конкретного объекта может путать пользователя. Компонент 208 фильтрации может использоваться также для удаления запросов, которые не представлены на желательном языке. Например, могут быть удалены все запросы, ассоциированные с объектами в возвращаемом наборе, относящемся к первоначальному запросу, которые содержат непечатаемые символы ASCII. Кроме того, для обеспечения того, чтобы наборы результатов связанных запросов были более сфокусированы, чем набор результатов, относящийся к первоначальному запросу, могут быть удалены связанные запросы, которые не являются по меньшей мере такими же длинными (по количеству слов), как первоначальный запрос.

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

Согласно фиг.3 иллюстрируется система 300, содействующая пользователю при поиске по нескольким объектам, осуществляемом таким пользователем. Система 300 использует запрос и набор результатов, ассоциированный с запросом, для выявления связанных запросов, которые использовались ранее. Связанные запросы ассоциированы с набором результатов, связанным с набором результатов первоначального запроса, но, по существу, не подобным ему. Система 300 включает в себя средство 302 поиска, которое принимает запрос. Средство 302 поиска осуществляет поиск по информационному хранилищу 304, содержащему совокупность объектов (например, документов, звуковых файлов, изображений, web-страниц, …), причем поиск по меньшей мере частично основан на принятом запросе. Каждый из объектов внутри информационного хранилища 304 ассоциирован с запросами, которые использовались ранее для выявления таких объектов. Например, ранее средством 302 поиска был использован запрос Q5, причем использование такого запроса привело к возврату объекта объект 4. Такая ассоциация объектов и запросов может храниться внутри информационного хранилища 304, внутри средства 302 поиска или любых других соответствующих местах хранения.

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

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

Система 300 дополнительно может быть ассоциирована с профилем 312 пользователя, который дополнительно конфигурирует систему 300 на индивидуальной основе в соответствии с предпочтением пользователя. Профиль 312 пользователя может хранить информацию, передаваемую в компонент 310 обратной связи, причем доступ к такому профилю пользователя может осуществляться независимо от устройства, которое использует пользователь. Например, пользователь может создать профиль 312 пользователя на настольном компьютере, находящемся в месте его пребывания. Однако использование профиля 312 пользователя не ограничивается этим конкретным настольным компьютером. Скорее пользователь может осуществлять доступ к такому профилю 312 пользователя из различных терминалов (например, персонального цифрового информационного устройства (PDA), другого компьютера, сотового телефона, …). Кроме того, профиль 312 пользователя может содержать компонент предыстории, который отслеживает поиски пользователя за предварительно определенный период времени. Соответственно, если пользователь прерывается во время поиска, такой пользователь может использовать профиль 312 пользователя для доступа к этому поиску в более поздний момент времени.

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

Соответственно, компонент 314 искуственного интеллекта может наблюдать за действиями пользователя и через какое-то время "узнавать" предпочтения пользователя, задаваемые конкретным контекстом и состоянием пользователя. Например, пользователь обычно может предпочитать просматривать некоторые типы объектов в определенные моменты времени дня и/или когда пользователь находится в определенных местоположениях. Компонент 314 искуственного интеллекта может принимать данные из различных датчиков(а) 316 (например, времени дня, местоположения пользователя, температуры …) и использовать такие данные для совершения соответствующего логического вывода. Например, пользователь, использующий PDA, может ввести в механизм 302 поиска запрос "катание на лыжах". Датчик(и) 316 (например, датчик GPS (глобальной системы позиционирования)) может определить, что пользователь находится в горах в штате Колорадо, что температура является прохладной и что время года соответствует сезону катания на лыжах по снегу. Соответственно, компонент 314 искуственного интеллекта может сделать логический вывод, что пользователю не должны возвращаться запросы, связанные с катанием на водных лыжах. В другом примере, пользователь, в основном, может по субботам после 3:00 пополудни осуществлять поиски по транзакциям (например, поиски по покупке и/или продаже товаров). Компонент 314 искуственного интеллекта может использовать такую информацию в связи с предоставлением пользователю оптимальных запросов, связанных с первоначальным запросом. Кроме того, компонент 314 искусственного интеллекта может применять анализ расхода/выгоды в отношении информирования средства 308 вычисления взаимосвязи в отношении того, какие запросы должны возвращаться пользователю. Более конкретно, компонент 314 искуственного интеллекта может приводить в соответствие выгоду от информирования средства 308 вычисления взаимосвязи о том, что конкретные запросы должны быть выбраны перед другими запросами, с расходом на необходимость изъятия требуемого запроса средством 308 вычисления взаимосвязи. После выявления нескольких запросов, которые являются связанными с первоначальным запросом и ассоциированы с наборами результатов, по существу, отличающимися по отношению к наборам результатов первоначального запроса, такие запросы могут быть возвращены пользователю посредством устройства 318 отображения.

Теперь согласно фиг.4 иллюстрируется система 400, обеспечивающая определение намерения пользователя при заданном конкретном запросе. Обычно пользователи предоставляют в средства поиска недоопределенные запросы, соответственно, делая затруднительным определение того, что намерен выявить пользователь. Система 400 использует запросы, которые использовались ранее для выявления объектов внутри возвращаемого набора, ассоциированного с недоопределенным запросом. Более конкретно, система 400 включает в себя средство 402 поиска, в которое поступает запрос. Запрос исходит от пользователя, программы извлечения текста или любого другого соответствующего средства, которое может формировать запрос. Средство 402 поиска использует запрос для выявления одного или большего количества объектов внутри информационного хранилища 404, причем объекты ассоциированы с запросами, которые использовались средством 402 поиска ранее для выявления таких объектов. Например, запросы Q1, Q2 и Q4 использовались ранее для выявления объекта объект 1. После выявления объектов, соответствующих запросу, средство 402 поиска использует компонент 406 ранжирования для ранжирования таких запросов. Согласно одному аспекту настоящего изобретения из набора результатов отбрасываются объекты, которые не превышают порога ранжирования. Средство 408 вычисления взаимосвязи просматривает запросы, использованные ранее для выявления объектов в наборе результатов, ассоциированном с первоначальным запросом. Средство 408 вычисления взаимосвязи ранжирует эти предыдущие запросы в соответствии с их уровнем взаимосвязи с первоначальным запросом и первоначальным набором результатов. Более конкретно, предыдущим запросам, связанным с первоначальным запросом и ассоциированным с наборами результатов, которые, по существу, не являются подобными набору результатов, ассоциированному с первоначальным запросом, дается более высокий ранг, чем несвязанным запросам. Например, для ранжирования предыдущих запросов может применяться показатель расстояния, используемый совместно с модифицированной схемой MMR. Наиболее высокоранжированные запросы могут быть возвращены пользователю через устройство 410 отображения.

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

Система 400 также содержит поисковый агент 414, используемый средством 402 поиска для гарантии того, что объекты не были удалены и/или изменены. Поисковые агенты являются программами, автоматически и систематически просматривающими информационное хранилище 404 (например, всемирную паутину (Wort Wite Web)). Поисковые агенты поддерживают копию всех посещенных объектов для последующей обработки, например, средством поиска. Поисковые агенты также используют эти объекты, чтобы способствовать сужению поиска. Средства поиска на основе поисковых агентов гарантируют, что объекты, возвращаемые при поиске, продолжают существовать внутри информационного хранилища 404 и являются текущими версиями таких объектов.

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

Согласно фиг.5 иллюстрируется система 500, которая обеспечивает возможность эффективного выявления объекта для пользователя через средство поиска. Система 500 включает в себя средство 502 поиска, которое принимает запрос. Средство 502 поиска использует такой запрос для выявления объектов внутри информационного хранилища 504, которые были посчитаны связанными с запросом. Каждый объект внутри информационного хранилища 504 ассоциирован с запросами, которые использовались ранее для выявления таких объектов. Например, запрос Q5 использовался средством 502 поиска ранее для выявления объекта объект 4. Средство 502 поиска включает в себя компонент 506 ранжирования, который ранжирует объекты, соответствующие запросу. Такой компонент 506 ранжирования может применять любой соответствующий алгоритм(ы) ранжирования в связи с выявлением и ранжированием объектов внутри информационного хранилища 504, соответствующих вводу запроса в средство 502 поиска.

После того как объекты выявлены, средством 508 вычисления взаимосвязи просматриваются запросы, ассоциированные с этими объектами. Средство 508 вычисления взаимосвязи выявляет запросы, являющиеся новыми и связанные с запросом, введенным в средство 502 поиска. Например, новые запросы ассоциированы с результатами, которые не включены в набор результатов, ассоциированный с введенным запросом. Связанные запросы ассоциированы с результатами, связанными с набором результатов, ассоциированным с введенным запросом. Например, для выявления новых, но связанных запросов, по сравнению с введенным запросом, могут быть применены показатель расстояния совместно с модифицированной схемой MMR. После выявления таких запросов они могут быть доставлены пользователю через устройство 510 отображения. После этого может быть осуществлен выбор таких запросов с использованием компонента 512 выбора запроса. Например, запросы могут быть отображены в виде ссылок, и компонент 512 выбора запроса способствует осуществлению выбора таких ссылок. После выбора запроса пользователю могут быть отображены результаты, ассоциированные с этим запросом, через устройство 510 отображения. Согласно одному конкретному аспекту настоящего изобретения выбранный запрос может быть введен в средство 502 поиска, вследствие этого обеспечивая пользователю возможность "углубления" в запросы, которые имеют большую определенность. Например, пользователя может интересовать, в частности, приманка для ужения нахлыстом. Однако сначала пользователь вводит в средство 502 поиска недоопределенный запрос "ужение нахлыстом". Средство 508 вычисления взаимосвязи извлекает запрос "приманки для ужения нахлыстом" и возвращает такой запрос пользователю. После этого пользователь выбирает запрос "приманки для ужения нахлыстом ", который направляется в средство 502 поиска. Затем средство 508 вычисления взаимосвязи может возвратить запросы, связанные с конкретными приманками, тем самым обеспечивая возможность быстрого получения пользователем объектов, ассоциированных с приманкой, которую такой пользователь был намерен выявить. Кроме того, средство 502 поиска может содержать память 514, в которой хранятся предыдущие поиски, осуществленные пользователем. Соответственно, если пользователь выбирает запрос и находит, что запрос возвращает объекты, не связанные с его намерением, он может просто вернуться на предыдущий уровень поиска. Например, если пользователю требуется выявить объект, ассоциированный с конкретной приманкой для ужения нахлыстом, но по выбранному запросу такой объект не был возвращен, то пользователь может вернуться к предыдущему выбранному запросу (например, "приманки для ужения нахлыстом ").

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

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

На этапе 606 просматриваются запросы, использованные ранее для извлечения объектов, возвращенных на этапе 604. Например, каждый объект ассоциирован с запросами, которые были использованы для выявления такого объекта. Соответственно, может существовать значительное количество запросов, связанных с каждым объектом. Кроме того, каждый ассоциированный запрос будет иметь возвращаемый набор (например, список объектов, которые возвращаются при использовании такого запроса). На этапе 608 делается определение относительно запросов, которые желательно возвратить пользователю. Желательные запросы ассоциированы с наборами результатов, связанными с набором результатов, соответствующим принятому запросу, хотя такие наборы результатов не являются, по существу, подобными набору результатов, соответствующему принятому запросу. Соответственно, желательные запросы должны извлекать и связанные, и новые объекты. Согласно одному аспекту настоящего изобретения для определения желательных запросов могут применяться показатели расстояния в связи с модифицированной схемой MMR. Более конкретно, для определения показателей расстояния может быть применен алгоритм:

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

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

q' q”

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

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

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

На этапе 708 извлекаются релевантные ассоциированные запросы и отображаются пользователю. Релевантные запросы должны быть связанными с принятым запросом, а также новыми относительно принятого запроса. Более конкретно, каждый ассоциированный запрос будет иметь соответствующий набор результатов (например, коллекцию объектов, которые возвращаются при использовании такого запроса). Наборы результатов соответствующих запросов должны быть связанными с набором результатов, соответствующим принятому запросу, но, по существу, не подобными ему. Кроме того, наборы результатов ассоциированных запросов должны быть связанными с наборами результатов, соответствующими другим ассоциированным запросам, но, по существу, не подобными им. Это обеспечивает то, что каждый возвращенный и отображенный запрос будет ассоциирован с объектами, которые не являются дубликатами, но, однако, являются связанными. Согласно одному аспекту настоящего изобретения, в связи с определением релевантных ассоциированных запросов могут применяться показатели расстояния совместно с модифицированной схемой MMR.

На этапе 710 пользователь выбирает один из ассоциированных запросов, причем такой ассоциированный запрос лучше представляет действительное намерение пользователя, чем запрос, принятый на этапе 702. Соответственно, пользователю будут предоставлены объекты, которые являются более релевантными намерению пользователя, чем объекты, возвращенные при использовании принятого запроса. На этапе 712 выявляются запросы, ассоциированные с выбранным запросом. Например, объект(ы), выявленный выбранным запросом, будет ассоциирован с другими запросами, которые использовались ранее для выявления такого объекта(ов). После этого на этапе 714 отображаются релевантные запросы, ассоциированные с выбранным запросом. Если применяются способы фильтрации, то релевантные запросы могут быть более определенными, чем выбранный запрос (например, запросы более короткие, чем выбранный запрос, могут быть исключены из рассмотрения). После этого, до тех пор, пока не будет выявлен оптимальный запрос, пользователь может выбирать, на этапе 710, другой запрос, лучше представляющий его намерение. Соответственно, пользователь может продолжать "углубляться" в запросы, пока не будет выявлен наилучший запрос. Методика 700 также преимущественна в ситуациях, в которых пользователь осуществляет просто просмотр. Например, пользователя может интересовать ужение нахлыстом, но он не имеет определенного намерения в отношении ужения нахлыстом. Пользователь может ввести в средство поиска общий запрос "ужение нахлыстом " и может быть представлена совокупность связанных запросов. Ассоциированные запросы могут содействовать просмотру пользователем в конкретном направлении.

Согласно фиг.8 иллюстрируется методика 800 для доставки запросов, связанных с конкретным объектом. На этапе 802 браузер ориентируется на конкретный сайт. Например, браузер может быть ориентирован через ввод URL в адресную строку такого браузера. В альтернативном варианте, пользователь может выбрать сайт после использования средства поиска для выявления такого сайта. На этапе 804 делается определение относительно того, использовались ли когда-либо какие-нибудь запросы для выявления такого сайта. Такая информация может быть выявлена, например, в информационном хранилище, доступном для браузера. Если не использовались, то методика заканчивается на этапе 806. Иначе, на этапе 808 извлекаются запросы, использованные ранее для выявления сайта. На этапе 810 выполняется анализ расхода/выгоды для определения того, является ли желательным отображение пользователю запросов во время просмотра таким пользователем выбранного сайта. Например, для оптимального просмотра может быть нежелательным отображение запросов совместно с сайтом, который требует существенного пространства экрана. Кроме того, предыстория пользователя может указывать, что пользователь предпочитает, чтобы запросы не представлялись совместно с выбранным сайтом.

На этапе 812 делается определение относительно того, желательно ли, в соответствии с анализом расхода/выгоды, представление запросов. Если нежелательно, то запросы не отображаются на этапе 814, и пользователю предоставляется только выбранный сайт. Если желательно, чтобы запросы были отображены, то на этапе 816 извлекаются релевантные запросы и отображаются пользователю на этапе 816. Например, в качестве запроса может быть выбран запрос с наименьшим количеством слов, и объекты, возвращенные в этом запросе, могут использоваться для выявления ассоциированных запросов. Более конкретно, пользователь может впечатать URL для сайта ужения нахлыстом на Аляске. После этого может быть просмотрено несколько запросов, использованных ранее для выявления такого сайта. В качестве базового запроса может быть использован наиболее короткий запрос (например, "ужение нахлыстом") и могут быть просмотрены все сайты, найденные таким запросом. После этого могут быть рассмотрены запросы, использованные ранее для того, чтобы найти такие сайты, и пользователю могут быть отображены запросы, связанные с базовым запросом. Соответственно, пользователю может быть предоставлено несколько запросов, связанных с сайтом, просматриваемым в данное время. Это может содействовать просмотру пользователем других сайтов, которые могут содержать релевантную информацию.

Согласно фиг.9 иллюстрируется возможное разбиение 900 (на части) набора результатов, ассоциированного с запросом, соответствующим предыдущим запросам. Средство 902 поиска принимает недоопределенный запрос и осуществляет поиск по коллекции объектов в соответствии с таким запросом. Как изображено на этом чертеже, недоопределенный запрос может привести к возврату многообразия объектов, которые могут быть связанными или не связанными с намерением пользователя (например, с запросом может быть связан широкий диапазон тем). Кроме того, недоопределенные запросы при использовании известных средств поиска могут приводить к возврату существенного количества документов. Например, при вводе в одно конкретное известное средство поиска, которое осуществляет поиск по Всемирной паутине, запрос "ужение нахлыстом" приводит к возврату более 3000000 объектов. Однако при использовании ранее использованных запросов (например, предыдущие пользователи использовали более определенные запросы, чем текущий пользователь) набор результатов может быть разбит на более определенные наборы результатов. Эти наборы результатов не только являются более конкретными в отношении темы, но, в основном, они включают в себя меньшее количество объектов. В этом конкретном разбиении 900 набор 904 результатов создан посредством использования недоопределенного запроса и средства 902 поиска. Однако с использованием настоящего изобретения набор результатов может быть разбит на несколько более определенных наборов 906-918 результатов. В частности, набор 906 результатов сформирован при использовании запроса M, набор 908 результатов сформирован при использовании средством 902 поиска запроса N, набор 910 результатов сформирован при использование запроса O, набор 912 результатов создан при использовании средством 902 поиска запроса P, набор 914 результатов сформирован при использовании запроса Q, набор 916 результатов создан при использовании запроса R и набор 918 результатов сформирован при использовании средством 902 поиска запроса S для совершения поиска по информационному хранилищу, содержащему объекты в наборе 918 результатов. Соответственно, пользователю предоставляются упомянутые запросы, которые могут содействовать фокусированию поиска пользователя на намерении пользователя.

Кроме того, должно быть понятно, что наборы 906-918 результатов могут быть сами разбиты в соответствии с предыдущими запросами пользователя, которые являются более конкретными. Также можно заметить, что наборы результатов, созданные посредством использования предыдущих запросов, могут быть полностью включены в первоначальный набор 904 результатов или частично могут находиться вне первоначального набора 904 результатов. Например, набор 906 результатов по запросу М частично лежит вне первоначального набора 904 результатов, в то время как набор 910 результатов по запросу O находится полностью в первоначальном наборе результатов. Кроме того, наборы результатов могут частично перекрываться друг с другом или полностью содержаться в другом наборе результатов. Например, наборы 908 и 910 результатов частично перекрываются.

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

Теперь, для облегчения более полного понимания одного или большего количества аспектов настоящего изобретения согласно фиг.11 иллюстрируется возможная компановка 1100 наборов результатов, соответствующих различным запросам. Компоновка включает в себя набор A 1102 результатов, извлеченный при использовании недоопределенного запроса A в связи со средством поиска. Например, набор A 1102 результатов может содержать пороговое число высокоранжированных объектов, в соответствии с алгоритмом(ами) ранжирования средства поиска. Однако это ограниченное число может охватывать широкий предмет темы внутри запроса. Например, если запросом A является "ужение нахлыстом", то верхние двадцать результатов могут охватывать широкий диапазон предмета внутри темы ужения нахлыстом. Однако запросы B и C являются более определенными, и, соответственно, они могут использоваться для извлечения наборов B 1104 и C 1106 результатов, которые также являются более определенными. Соответственно, например, пользователь может первоначально ввести запрос и ему будет доставлена по меньшей мере часть набора A 1102 результатов. Пользователю также могут быть предоставлены запросы B и C, которые могут быть более определенными и лучше представлять намерение пользователя. Пользователь может выбрать использование запроса B и/или запроса C для получения результатов, что должно способствовать более быстрому выявлению требуемого объекта, чем использование запроса A. Кроме того, запросы B и C могут быть также связанными друг с другом, что приводит по меньшей мере к частичному перекрытию набора B 1104 результатов и набора C 1106 результатов.

Как иллюстрируется на этом чертеже, набор B 1104 результатов может быть разбит дополнительно с использованием запросов D и E, а набор C результатов может быть разбит дополнительно с использованием запросов D, F и G. Упомянутые запросы, в свою очередь, формируют набор D 1108 результатов, набор E 1110 результатов, набор F 1112 результатов и набор G 1114 результатов. Упомянутые наборы 1108-1114 результатов являются разделениями набора B 1104 результатов и набора C 1106 результатов, и, следовательно, разделениями набора A 1102 результатов. Кроме того, набор E 1110 результатов и набор F 1112 результатов могут по меньшей мере частично перекрываться, и набор F 1112 результатов и набор G 1114 результатов могут по меньшей мере частично перекрываться. В одном примере, пользователь может ввести запрос A и получить набор A 1102 результатов, содержащий объекты, не сильно связанные с намерением пользователя. Предоставляются запросы B и C и после просмотра таких запросов пользователь может определить, что один из них лучше представляет намерение пользователя. После этого пользователь может выбрать запрос B и получить набор B 1104 результатов, а также ему предоставляются запросы D и E, которые могут еще лучше представлять намерение пользователя. Если выбирается запрос E, то пользователю может быть отображен набор E 1110 результатов, который содержит объекты, сильно связанные с намерением пользователя.

Согласно фиг.12 иллюстрируется другое возможное использование 1200 настоящего изобретения. Набор 1202 результатов по недоопределенному запросу A формируется при использовании средством поиска недоопределенного запроса A в связи с поиском. Настоящее изобретение обеспечивает разбиение набора результатов на несколько более определенных наборов результатов на основе предыдущих запросов, использованных для выявления объектов внутри наборов результатов. Например, набор 1204 результатов может быть создан при использовании предыдущего запроса M в связи со средством поиска, набор 1206 результатов может быть сформирован при использовании для поиска предыдущего запроса N и набор 1208 результатов может быть создан при использовании предыдущего запроса O для поиска по коллекции объектов. Например, запросом A может быть "ужение нахлыстом", запросом M может быть "как осуществлять ужение нахлыстом", запросом N может быть "сообщения об ужении нахлыстом" и запросом O может быть "насекомые для форели". Все эти запросы являются связанными с ужением нахлыстом и могут использоваться для содействия пользователю в выявлении конкретного объекта. Упомянутые наборы 1204-1208 результатов могут использоваться также для выявления запроса P, который является косвенно связанным с ужением нахлыстом. Это может быть выполнено, например, посредством просмотра входящих ссылок и исходящих ссылок от объектов внутри возвращаемых наборов 1204 - 1208. В этом конкретном примере, объекты внутри набора 1204 результатов и набора 1208 результатов имеют входящие ссылки и/или исходящие ссылки к существенному количеству объектов внутри набора 1210 результатов по запросу P. Например, как раньше, запросом M может быть "как осуществлять ужение нахлыстом" и запросом O может быть "насекомые для форели". Совокупность объектов внутри наборов 1204 и 1208 результатов могут содержать исходящие ссылки на объекты «морского лова рыбы”, которые являются только косвенно связанными с ужением нахлыстом. Существенное количество этих объектов может быть найдено с использованием одного запроса P (например, "морской лов рыбы на Восточном Побережье"). Настоящее изобретение предполагает просмотр входящих ссылок и/или исходящих ссылок внутри разбитого на части набора результатов для представления пользователю одного или большего количества запросов, которые являются косвенно связанными с первоначальным запросом A. Это может быть выгодно, когда пользователь не имеет конкретного намерения, а просто просматривает коллекцию объектов, пока не посчитает один такой объект интересным.

Теперь, согласно фиг.13 иллюстрируется возможная реализация 1300 изобретения. Первоначальный недоопределенный запрос 1302 в реализации 1300 отображен по верхней части как "ужение нахлыстом" (“fly fishing”). Непосредственно ниже запроса находится список запросов 1304, которые связаны с первоначальным запросом "ужение нахлыстом", но не возвращают, по существу, подобные результаты (например, десять наиболее высокоранжированных результатов из запроса "ужение нахлыстом" и десять наиболее высокоранжированных результатов, возвращаемых при использовании запросов 1304, не являются, по существу, подобными). Упомянутые запросы 1304 снабжаются гиперссылками, причем выбор одного из запросов направляет пользователя к другой части возвращенной страницы. Кроме того, выбор одного из запросов может привести к полностью новому поиску с другими связанными запросами, выявляемыми и отображаемыми пользователю. Ниже списка запросов 1304 находится целое число результатов 1306 поиска по запросу "ужение нахлыстом". Эти результаты возвращены для случаев, что пользователь знает, что посредством использования запроса "ужение нахлыстом" может быть найден конкретный объект.

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

Теперь, согласно фиг.14 иллюстрируется другая возможная реализация 1400 настоящего изобретения. Используется браузер 1402, содержащий адресную строку 1404, которая может использоваться для введения URL требуемого сайта для посещения его во Всемирной паутине. Браузер может быть ориентирован на страницу посредством ввода адреса в адресную строку 1404, выбора ссылки из другого сайта, с использованием средства поиска и т.д. Браузер 1402 включает в себя область 1406 отображения, отображающую сайт, соответствующий URL. Браузер 1402 также включает в себя область 1408 отображения, которая может использоваться для отображения запросов, использованных ранее для выявления такого сайта. Например, в качестве базового запроса может быть задействован наиболее короткий запрос, который может использоваться для извлечения сайта, и по меньшей мере частично на основе базового запроса могут быть определены связанные запросы, которые также могут использоваться для приема сайта. Соответственно, если пользователь предпочитает информацию, подобную показанной в области 1406 отображения, для выявления такой информации, такой пользователь может просто выбрать запрос из области 1408 отображения.

Теперь, согласно фиг.15 и 16 иллюстрируются возможные реализации настоящего изобретения, причем такие возможные реализации обеспечивают пользователю возможность управления объемом требуемого перекрытия между возвращаемыми наборами первоначального запроса и связанных запросов. Такие реализации обеспечивают возможность конфигурирования пользователем средства поиска на индивидуальной основе посредством управления уровнем случайности между первоначальным запросом и извлеченными запросами. Более конкретно, требование существенного перекрытия между возвращаемыми наборами для первоначального запроса и предыдущих запросов приведет к извлечению подобных запросов, в то же время требование меньшего объема перекрытия между такими возвращаемыми наборами приведет к извлечению более случайно связанных запросов. Согласно фиг.15 одна конкретная возможная реализация 1500 настоящего изобретения включает в себя окно 1502 запроса (QUERY), в которое пользователь ввел запрос "медовый месяц" (”Loneymoon”). Для управления объемом требуемого перекрытия между возвращаемыми наборами для первоначального запроса "медовый месяц" и предыдущих запросов пользователем может использоваться ползунковый регулятор 1504, называемый "измерителем случайности" (“Serendipitometer”). Например, в этой возможной реализации ползунковый регулятор 1504 позиционирован так, чтобы требовался существенный объем перекрытия между возвращаемым набором для запроса "медовый месяц" и предыдущими запросами (например, пользователю будут возвращены менее случайные запросы). Более конкретно, первоначальный запрос "медовый месяц" приводит к совокупности подобных запросов 1506, например, "медовые месяцы", "места для проведения медового месяца", "свадебные контракты", "свадебные круизы", "романтический отдых" и "курорты для медового месяца". Как может быть определено при просмотре таких запросов, они, в основном, более определенны относительно первоначального запроса "медовый месяц" и могут использоваться пользователем для "углубления" до выявления запроса, отражающего его/ее намерение. Кроме того, для случаев, когда первоначальным запросом был возвращен желаемый объект, пользователю возвращается совокупность высокоранжированных объектов 1508, выявленных посредством использования запроса "медовый месяц".

Теперь, согласно фиг.16 иллюстрируется другая возможная реализация 1600 настоящего изобретения. В окно 1502 запроса вновь введен запрос "медовый месяц", но ползунковый регулятор 1504 был позиционирован так, чтобы требовался меньший объем перекрытия между возвращаемыми наборами для первоначального запроса ("медовый месяц") и предыдущих запросов. Это допускает то, чтобы совокупность запросов 1504 была случайно связана с первоначальным запросом (например, запросы, которые могут предоставить пользователю полезную информацию, которую такой пользователь не имел определенного намерения найти). В этом возможном варианте осуществления возвращаемые запросы, такие как "заявления на паспорт", "Оаху" и "дешевые рейсы" не могут быть непосредственно связаны с пользователем, но такой пользователь может найти такую информацию полезной. Например, при просмотре мест для проведения медового месяца пользователь может предпочесть поехать заграницу, но еще не подумал о заявлениях на паспорт. Следовательно, настоящее изобретение может использоваться для содействия пользователю в нахождении информации, косвенно связанной с намерением пользователя. Хотя возможные реализации 1500 (фиг.15) и 1600 используют ползунковый регулятор 1504, должно быть понятно, что могут использоваться любые соответствующие средства для обеспечения возможности изменения пользователем уровня требуемого перекрытия между возвращаемыми наборами для первоначального запроса и предыдущих запросов. Кроме того, уровень требуемого перекрытия между возвращаемыми наборами для первоначального запроса и предыдущих запросов может определяться автоматически посредством компонента(ов) искуственного интеллекта через наблюдение за действиями пользователя за некоторое время и изучение типов желательных для пользователя запросов при заданных конкретных состояниях и/или контекстах.

Согласно фиг.17 иллюстративная среда 1710 для реализации различных аспектов изобретения включает в себя компьютер 1712. Компьютером 1712 может быть любое соответствующее вычислительное устройство (например, персональное цифровое информационное устройство, портативный компьютер, сервер, настольный компьютер, …). Компьютер 1712 включает в себя процессор 1714, системную память 1716 и системную шину 1718. Системная шина 1718 соединяет компоненты системы, в том числе системную память 1716, с процессором 1714. Процессором 1714 может быть любой из различных доступных процессоров. В качестве процессора 1714 также могут использоваться сдвоенные микропроцессоры и другие многопроцессорные архитектуры.

Системная шина 1718 может быть любой из нескольких типов структур шин, включая шину памяти или контроллер памяти, периферийную шину или внешнюю шину и/или локальную шину, используя любую из многих доступных архитектур шин, включая 8-битовую шину, шину архитектуры A, соответствующей промышленному стандарту (ISA), шину микроканальной архитектуры (MCA), шину расширенной ISA (EISA), интеллектуальный интерфейс накопителей (IDE), локальную шину Ассоциации по стандартам в области видеоэлектроники (VESA), шину межсоединения периферийных компонентов (PCI), универсальную последовательную шину (USB), усовершенствованный графический порт (AGP), шину Международной ассоциации производителей плат памяти для персональных компьютеров (PCMCIA) и интерфейс малых компьютерных систем (SCSI) и т.д.

Системная память 1716 включает в себя энергозависимую память 1720 и энергонезависимую память 1722. В энергонезависимой памяти 1722 хранится базовая система ввода/вывода (BIOS), в которой содержатся основные процедуры для передачи информации между элементами внутри компьютера 1712, например, при запуске. В виде иллюстрации, энергонезависимая память 1722 может включать в себя постоянное запоминающее устройство (ПЗУ, ROM), программируемое ПЗУ (PROM), электрически программируемое ПЗУ (EPROM), электрически стираемое программируемое ПЗУ (EEPROM) или флэш-память и т.д. Энергозависимая память 1720 включает в себя оперативное запоминающее устройство (ОЗУ, RAM), действующее как внешняя кэш-память. В виде иллюстрации, ОЗУ доступно во многих видах, таких как синхронное ОЗУ (SRAM), динамическое ОЗУ (ДОЗУ, DRAM), синхронное ДОЗУ (СДОЗУ, SDRAM), СДОЗУ с удвоенной скоростью передачи данных (DDR SDRAM), расширенное СДОЗУ (ESDRAM), ДОЗУ Synchlink (SLDRAM) и ОЗУ Direct Rambus (DRRAM) и т.д.

Компьютер 1712 также содержит съемные/несъемные, энергозависимые/энергонезависимые компьютерные носители информации. Фиг.17 иллюстрирует, например, накопитель 1724 на дисках. Накопитель 1724 на дисках включает в себя устройства, такие как магнитный дисковод, дисковод для гибких дисков, устройство считывания магнитной ленты, дисковод Jaz, дисковод zip, дисковод LS-100, карточка флэш-памяти или карта памяти Memory Stick и т.д. Дополнительно, накопитель 1724 на дисках может включать в себя носители информации отдельно или в комбинации с другим носителями информации, включая, но не в ограничительном смысле оптический дисковод, такой как устройство чтения ПЗУ на компакт-диске (CD-ROM), дисковод для записываемых компакт-дисков (CD-R), дисковод для перезаписываемых компакт-дисков (CD-RW) или дисковод для чтения ПЗУ на универсальном цифровом диске (DVD-ROM) и т.д. Для обеспечения подсоединения устройств-накопителей 1724 на дисках к системной шине 1718 обычно используется интерфейс памяти съемно или несъемно, например, интерфейс 1726.

Должно быть ясно, что фиг.17 изображает программное обеспечение, действующее в качестве посредника между пользователями и основными ресурсами компьютера, изображенными в соответствующей рабочей среде 1710. Такое программное обеспечение включает в себя операционную систему 1728. Операционная система 1728, которая может храниться на накопителе 1724 на дисках, действует для управления и распределения ресурсов вычислительной системы 1712. Системные приложения 1730 используют преимущества управления ресурсами операционной системой 1728 через программные модули 1732 и данные 1734 программ, которые хранятся или в системной памяти 1716, или на накопителе 1724 на дисках. Ясно, что настоящее изобретение может быть реализовано различными операционными системами или комбинациями операционных систем.

Пользователь вводит команды или информацию в компьютер 1712 через устройство(а) 1736 ввода данных. Устройства 1736 ввода данных включают в себя, например, указательное устройство, такое как мышь, шаровой манипулятор, перо, сенсорную клавишную панель, клавиатуру, микрофон, джойстик, игровую клавишную панель, спутниковую антенну, сканер, плату селектора телевизионных каналов, цифровую камеру, цифровую видеокамеру, web-камеру и т.д. Эти и другие устройства ввода данных подсоединяются к процессору 1714 посредством системной шины 1718 через интерфейсный порт(ы) 1738. Интерфейсный порт(ы) 1738 включает в себя, например, последовательный порт, параллельный порт, игровой порт и универсальную последовательную шину (USB). Устройство(а) 1740 вывода данных использует некоторые из типов портов, идентичных используемым устройством(ами) 1736 ввода данных. Соответственно, например, для обеспечения ввода в компьютер 1712 и для вывода информации из компьютера 1712 на устройство 1740 вывода данных может использоваться порт USB. Для иллюстрации наличия некоторых устройств 1740 вывода данных, таких как мониторы, динамики и принтеры, среди других устройств 1740 вывода данных, которые требуют специальных адаптеров, обеспечен выходной адаптер 1742. Выходные адаптеры 1742 включают в себя, например, видео и звуковые платы и т.д., обеспечивающие средство соединения между устройством 1740 вывода данных и системной шиной 1718. Следует отметить, что другие устройства и/или системы устройств обеспечивают возможности и ввода и вывода данных, например, удаленный компьютер(ы) 1744.

Компьютер 1712 может функционировать в сетевой среде, используя логические соединения с одним или большим количеством удаленных компьютеров, например, удаленным компьютером(ами) 1744. Удаленный компьютер(ы) 1744 может быть персональным компьютером, сервером, маршрутизатором, сетевым персональным компьютером (PC), рабочей станцией, устройством, основанным на микропроцессорах, одноранговым устройством или другим общим сетевым узлом и т.д., и обычно содержит многие или все из элементов, описанные в отношении компьютера 1712. Для краткости, в удаленном компьютере(ах) 1744 изображено только запоминающее устройство 1746. Удаленный компьютер(ы) 1744 соединен с компьютером 1712 логически посредством сетевого интерфейса 1748 и к тому же соединен физически через соединение 1750 связи. Сетевой интерфейс 1748 охватывает сети связи, такие как локальные сети (ЛС, LAN) и глобальные сети (ГС, WAN). Технологии LAN включают в себя распределенный интерфейс передачи данных по волоконно-оптическим каналам (FDDI), распределенный проводной интерфейс передачи данных (CDDI), Ethernet/IEEE 802.3, Token Ring (маркерное кольцо)/IEEE 802.5 и т.д. Технологии WAN включают в себя линии связи “точка - точка”, сети связи с коммутацией каналов, такие как Цифровая сеть с интеграцией служб (ISDN) и ее вариации, сети связи с коммутацией пакетов и Цифровые абонентские линии связи (DSL) и т.д.

Соединение(я) 1750 связи относится к аппаратным средствам/программному обеспечению, используемым для соединения сетевого интерфейса 1748 с шиной 1718. Хотя, в целях пояснения, для ясности соединение 1750 связи изображено внутри компьютера 1712, оно может быть также внешним относительно компьютера 1712. Аппаратные средства/программное обеспечение, необходимые для соединения с сетевым интерфейсом 1748, включают в себя, исключительно в качестве примера, внутренние и внешние технологии, такие как модемы, включая телефонные модемы стандартного качества, кабельные модемы и модемы DSL, адаптеры ISDN и платы Ethernet.

Фиг.18 - схематическая блочная диаграмма типовой вычислительной среды 1800, с которой может взаимодействовать настоящее изобретение. Система 1800 содержит один клиент 1810 или большее количество клиентов 1810. Клиент(ы) 1810 могут быть аппаратными и/или программными (например, потоки, процессы, вычислительные устройства). Система 1800 также содержит один сервер 1830 или большее количество серверов 1830. Сервер(ы) 1830 также могут быть аппаратными и/или программными (например, потоки, процессы, вычислительные устройства). Сервера 1830 могут вмещать потоки для выполнения преобразований, например, с использованием настоящего изобретения. Одна возможная связь между клиентом 1810 и сервером 1830 может осуществляться в виде пакета данных, адаптированного для передачи между двумя или большим количеством вычислительных процессов. Система 1800 включает в себя инфраструктуру 1850 связи, которая может использоваться, для обеспечения связи между клиентом(ами) 1810 и сервером(ами) 1830. Клиент(ы) 1810 в рабочем состоянии соединены с одним информационным хранилищем 1860 клиента или большим количеством информационных хранилищ 1860 клиента, которые могут использоваться для хранения информации, локальной для клиента(ов) 1810. Аналогично, сервер(а) 1830 в рабочем состоянии соединен с одним информационным хранилищем 1840 сервера или большим количеством информационных хранилищ 1840 сервера, которые могут использоваться для хранения информации, локальной для серверов 1830.

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

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

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

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

3. Система по п.2, в которой показатели расстояния определяются посредством применения алгоритма

где - показатель расстояния между запросом q пользователя на поиск и одним или более прежде использованными запросами q', a R - бинарное отношение на Q×D, где Q - набор запросов, использованных средством поиска прежде, а D - набор объектов внутри информационного хранилища, по которому средством поиска осуществляется поиск.

4. Система по п.3, в которой уровень связанности получается по меньшей мере частично посредством применения модифицированной схемы максимальной граничной релевантности.

5. Система по п.4, в которой модифицированной схемой максимальной граничной релевантности применяется алгоритм
,
где λ - коэффициент интерполяции, установленный априорно, и q” - один или более прежде использованных запросов, которые уже были рассмотрены до рассмотрения q'.

6. Система по п.1, в которой упомянутые объекты содержат одно или более из документов, звуков, видеоданных, изображений и web-сайтов.

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

8. Система по п.1, в которой информационное хранилище является одним из сети Интернет, сети интранет, сервера и накопителя на жестких дисках.

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

10. Система по п.9, в которой компонент случайности является изменяемым пользователем.

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

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

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

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

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

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

17. Система по п.1, дополнительно содержащая компонент фильтрации, исключающий из рассмотрения прежде использованные запросы, которые содержат символы, являющиеся непечатаемыми символами ASCII.

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

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

20. Система по п.19, в которой контекстная информация содержит одно или более из температуры, времени суток, местоположения и дня недели.

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

22. Система по п.21, в которой профиль пользователя является переносимым.

23. Система по п.1, дополнительно содержащая средство ассоциирования упомянутых объектов с запросами, использованными прежде для выявления таких объектов.

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

25. Система по п.1, которая хранится на клиенте.

26. Система по п.1, реализованная в сотовом телефоне.

27. Система по п.1, реализованная в персональном цифровом информационном устройстве.

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

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

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

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

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

33. Способ по п.28, в котором информационное хранилище является одним из сети Интернет, сети интранет, сервера и накопителя на жестких дисках.

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

35. Машиночитаемый носитель информации, на котором хранятся машиноисполняемые команды, которыми, при их исполнении одним или более процессорами, реализуется способ по п.28.