Перепечатано из http://www.citforum.ru/
Сергей Кузнецов

Обзор октябрьского 2005 г. номера журнала Computer (IEEE Computer Society, V. 38, No 10, Окябрь, 2005)

На обложке октябрьского выпуска журнала тема номера обозначена как “Рубежи поиска” (“Frontiers of Search”). Этой теме посвящены пять больших статей плюс небольшая заметка приглашенного редактора Нарена Рамакришнана (Naren Ramakrishnan, Virginia Tech). Во вводной заметке редактора отмечается, что поисковые процессоры являются широко распространенными универсальными интерфейсами к информации, не связанными с конкретными категориями пользователей, географическими областями или целями поиска информации. Поэтому развитие технологии поиска представляет интерес для любого пользователя Internet, а не только для технических профессионалов. Специальный выпуск журнала Computer, посвященный поисковым серверам, позволяет составить картину текущих тенденций и понять, как они повлияют на использование Internet в будущем.

Первая статья тематической подборки называется “Спам: теперь он не только в почтовых ящиках” (“Spam: It’s Not Just for Inboxes Anymore”) и написана Золтаном Гьенги и Гектором Гарсиа-Молина (Zoltan Gyongyi, Hector Garcia-Molina, Stanford University). (Надеюсь, что имя второго автора знакомо всем читателям, которые когда-либо интересовались тематикой баз данных и информационных систем.) Несмотря на обещания софтверных компаний и поставщиков услуг, спам в электронной почте настолько же привычен и надоедлив, как и поток рекламных воззваний в обычной почте, и настолько же неизбежен. Однако часто удивляет и даже немного пугает, когда невинный поиск ближайшей шиномонтажной мастерской приводит тебя на страницу с повышенными процентными ставками по закладным, недорогими лекарствами, юридической помощью или болезненной косметической хирургией. Это похоже на то, как если бы вы кликнули по всем наихудшим линкам в своем почтовом ящике, и кто знает, что происходит за кулисами, пока вы находитесь на нежеланной странице? Наши поздравления, вы стали жертвой Web-спама.

На первый взгляд, это похоже на вопиющее злоупотребление поискового процессора, но при более пристальном рассмотрении складывается немного более размытая картина. Некоторые виды Web-спама являются очевидной диверсией. Например, в одном из экспериментов авторов в ответ на запрос в Google “Kaiser pharmacy online” выдавалась страница, выглядевшая в точности так же, как результирующая страница Google, на с заголовком “Gogle”, и все ссылки вели на несколько сайтов, продающих дешевые лекарства по рецептам. Ясно, что такая подстановка неточной результирующей страницы является попыткой подрыва репутации Google и заслуживает метки “спам”.

В качестве примера не столь очевидной ситуации авторы рассматривают Web-сайт World News Network (WNN), ссылка на которой выдается в Google третьей в списке в ответе на запросы “world news” и “news network” в компании таких известных новостных ресурсов, как BBC, CNN и Fox. Но WNN в действительности не является новостным ресурсом; это компания, владеющая несколькими тысячами Web-сайтов, каждый из которых представляет собой онлайновую газету, посвященную конкретным темам конкретной географической области. При более тщательном анализе оказалось, что большая часть контента этих локальных изданий посвящена не местным бизнес-новостям, а более общим событиям, таким как война в Ираке. Эти сайты тесно связаны между собой, но на них не ссылаются сайты, не относящиеся к WNN. Хотя все статьи поступают из уважаемых источников, таких как Associated Press, CNN и New York Times, редко встречаются ссылки на реальные источники. Авторы считают WNN примером “серой зоны” Internet: агрегация новостей может быть полезной, но обеспечивает ли WNN что-либо действительно ценное или же существует, главным образом, для получения дохода от размещения рекламы на своих страницах?

Размытость картины спама дополняют субъективность искателей информации и аспект свободы самовыражения. При задании Google и Yahoo запроса “miserable failure” (“плачевная неудача”) на первом или втором месте в ответе появляется ссылка на официальную биографию президента Джорджа Буша. Конечно, методы спама влияют на ранжирование результатов поиска, но данный случай не является очевидным примером Web-спама, поскольку одобрение или порицание чего бы то ни было зависят от индивидуальных предпочтений. Так что и странный результат является все-таки результатом, представляющим некоторую ценность.

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

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

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

В сообществе поисковых служб полагают, что Web-спам будет становиться все более распространенным и изощренным. Это мнение подтверждают статистические данные. Статистические отчеты показывают, что в 2002 г. поисковые серверы индексировали от 6 до 8 процентов страниц спама, в 2003-2004 гг. спам составил уже 15-18%. В другом исследовании обнаружено, что примерно в девяти процентах результатов поиска среди первых 10 выданных ссылок содержалась, по крайней мере, одна ссылка на спам, а в 68% случаев ссылки на спам содержались среди первых 200 ссылок.

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

Авторы следующей статьи Роберт Капра и Мануэль Перез-Квинонес (Robert G. Capra III, Manuel A. Perez-Quinones, Virginia Tech). Название статьи – “Использование поисковых серверов для нахождения и повторного нахождения информации” (“Using Web Search Engines to Find and Refind Information”).
Поисковые серверы, получающие в день около 550 миллионов запросов, играют решающую роль в обнаружении и фильтрации огромного объема данных, доступных во Всемирной паутине. Однако, несмотря на доступность все более точных и эффективных алгоритмов поиска, даже опытные пользователи испытывают затруднения при повторном нахождении информации, ранее найденной в Web. Более того, часто пользователи не знают, как получить повторный доступ к требуемым им данным. Даже если пользователи осознают ценность информации, они часто испытывают трудности при использовании существующих организационных инструментов, подобных закладкам.

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

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

В этой исследовательской работе участвует и Центр человеко-машинных взаимодействий Политехнического института и государственного университета штата Верджиния (www.hci.vt.edu), где исследуется процессы нахождения и повторного нахождения пользователями данных в Web и факторы, влияющие на эти процессы. Объединив собственные результаты с результатами родственных исследований, авторы разработали модель использования поискового сервера, основанную на том, насколько часто пользователи выполняет заданную задачу и насколько они знакомы со способами ее выполнения.

Статью “Интеллектуальные поисковые агенты, использующие управляемые Web пояснительные диалоги на естественном языке” (“Intelligent Search Agents Using Web-Driven Natural-Language Explanatory Dialogs”) представили Анита Феррейра и Джон Аткинсон (Anita Ferreira, John Atkinson, Universidad de Concepcion, Chile).

Ускоренный рост World Wide Web превращает Internet в необъятное информационное пространство с разнотипным и зачастую плохо организованным содержимым. Пользователи сталкиваются с быстро возрастающими объемами информации, что характеризуется терминов “информационная перегрузка”. Хотя для обхода отдельных Web-сайтов пользователям оказывается достаточным минимальное обучение, для поиска информации на основе запросов и навигации между сайтами требуется больший опыт.

Для эффективного использования поисковых серверов, таких как AltaVista или Excite, нужно обладать углубленными знаниями. Результаты исследований поискового поведения опытных и начинающих пользователей Web могут иметь несколько практических приложений. Модель поискового поведения может служить основой совершенствования интерфейсов и функциональности существующих поисковых систем. Более совершенные будущие системы смогут определять изменяющиеся потребности и опытных, и начинающих пользователей. Кроме того, в системах подсказок можно извлечь пользу от лучшего понимания затруднений пользователей в процессе поиска.

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

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

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

Бхарат Кумар Мохан (Bharath Kumar Mohan, Indian Institute of Science, Bangalore) написал статью “Поиск воспитателей в сетях ассоциаций” (“Searching Association Networks for Nurturers”).

Поиск в Web включает не только просеивание огромного графа страниц и гиперссылок. Появляются специальные сети ассоциаций, более качественно обслуживающие запросы, специфичные для конкретной предметной области, путем использования принципов и паттернов, применимых в этой области. Особенно полезным может быть поиск в таких сетях ассоциаций с целью нахождения “воспитателей” (nurturer) – первопроходцев (early adopter). Появляющиеся вокруг этих “воспитателей” новые узлы также становятся важными в сети. Нахождение “воспитателей” может улучшить поиск в Web, особенно при обеспечении ответов на “вязкие” (sticky) запросы – постоянный поиск, от которого пользователь ожидает часто получать свежие обновления.

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

В качестве примеров приводятся поисковый сервер ZoomInfo (zoominfo.com), который обеспечивает наилучшие результаты при поиске информации о принадлежности людей к организациям, обнаруживая соответствующие данные в Web; специализированные торговые сайты ориентированы на обеспечение ответов относительно различных категорий товаров; сайты, подобные CiteSeer и Google Scholar, обеспечивают точную информацию о ранжировании исследовательских статей, основываясь на индексах цитируемости, и т.д. В каждой из этих вертикалей поиска улучшению результатов способствует использование знания и понимания особенностей предметной области.

С точки зрения поискового сервера Web представляет собой множество перекрывающихся сетей ассоциаций, каждая из которых может обеспечивать ответы на различные запросы. Для улучшения обработки запросов базовая сеть ассоциаций Web “страница-гиперссылка-страница” уточняется более конкретными сущностями и связями. Хотя такие сети расширяют возможности поиска и повышают его точность, их оказывается недостаточно для обработки “вязких” запросов. Подобные запросы могут затрагивать блоги, касающиеся практических приемов программирования и проектирования программных систем; многообещающие и развивающиеся технологии; сенсационные новости; информацию о выпускниках университетов, специализирующихся в области поиска в Web; данные о новых кинофильмах и т.д. Для выполнения таких запросов нельзя использовать ранжирование на основе анализа ссылок, поскольку в ассоциативных сетях обычно бывает мало ссылок на свежие документы.

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

Последняя статья тематической подборки называется “Поиск в Semantic Web” (“Search on the Semantic Web”). У статьи шесть авторов, все они из Мэрилендского университета. Как обычно для подобных случаев, укажу имя только первого автора: Ли Динг (Li Ding). По мере развития инфраструктуры Web поисковые серверы стали играть в ней центральную роль. В начале эпохи Web люди искали интересующие их страницы путем навигации от страниц с запомненными адресами. Быстрый рост числа страниц привел к появлению Web-каталогов, подобных Yahoo, в которых вручную организовывались тематические иерархии ссылок на Web-страницы. Продолжающийся рост Web заставил пополнить эти каталоги поисковыми серверами, такими как Lycos, HotBot и AltaVista, автоматически обнаруживающими новые и измененные Web-страницы, добавляющими ссылки на них в базу данных и индексирующими их по ключевым словам и свойствам. Сегодня в инфраструктуре Web доминируют такие поисковые серверы, как Google и Yahoo, которые в значительной степени определяют современное восприятие Web.

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

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

Во-вторых, знания, представленные на языках Semantic Web, например, на языке RDF (Resource Description Framework) отличаются как от неструктурированного текста, размещаемого на большинстве Web-страниц, так и от полностью структурированной информации, хранящейся в базах данных. Для работы с такой полуструктурированной информацией требуются развитые методы индексирования и выборки. В RDF, RDF Schema и OWL (Web Ontology Language) присутствуют семантические возможности, выходящие за пределы возможностей обычного XML. Эти возможности позволяют определять термины, связи между ними, вводить ограничения и аксиомы, которые должны соблюдаться для правильно построенных данных.

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

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

В поисковом сервере Swoogle для Semantic Web, разработанном группой eBiquity Мэрилендского университета, используется не один унифицированный метод поиска, а стратегия, включающая четыре аспекта: выполнение метапоиска над традиционными поисковыми серверами Web для нахождения кандидатов; использование специализированного механизма поиска для обхода каталогов, в которых обнаруживаются семантические документы; сбор URL при обработке обнаруженных семантических документов; сбор URL семантических документов и каталогов, содержащих семантические документы, представленные пользователями. Для оказания помощи пользователям и программным агентам для нахождения требуемого знания в Semantic Web Swoogle обнаруживает, индексирует и анализирует онтологии и факты, содержащиеся в семантических документах.

Единственная большая статья октябрьского номера, не вошедшая в тематическую подборку, написана большой группой авторов из компании Cluster Technology Ltd (Гонконг) и университета Гонконга. Первый автор: Монк-Пинг Леонг (Monk-Ping Leong). Статья называется ” CPE: параллельная библиотека для приложений финансовой инженерии” (“CPE: A Parallel Library for Financial Engineering Applications”).

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

Параллельная среда, разработанная компанией Cluster Tech, (Clustertech parallel environment, CPE) является библиотекой классов C++, облегчающей разработку крупномасштабных параллельных приложений, в частности, приложений финансовой инженерии. При создании CPE преследовались цели обеспечения эффективности и переносимости. В настоящее время CPE может использоваться на платформах ОС Unix, Linux и Windows, обеспечивая ориентированные на прикладную область объектно-ориентированные библиотеки для решения дифференциальных уравнений в частных производных и стохастических дифференциальных уравнений конечно-разностными (Finite-Difference, FD) методами и методом Монте-Карло (Monte Carlo, MC). Обеспечивается единая реализация операций, общих для методов FD и MC, так что в большинстве случаев от пользователя требуется только обеспечение кода, специфичного для данного приложения.

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

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

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