Обзор апрельского номера журнала Computer, 2004 г. (IEEE Computer Society, Vol. 37, No. 4, April 2004)
Тема апрельского номера обозначена как Putting the Web to Work («Приведение Web в действие»). Впрочем, с Сетью связаны только три из шести больших статей, и их тематика очень неоднородна.
Первая статья называется «Инфраструктура программного обеспечения для аутентифицируемого снятия показаний в Web» (A Software Infrastructure for Authenticated Web Metering). Ее авторы — Карло Блундо (Carlo Blundo) и Стельвио Кимато (Stelvio Cimato). Развитие рекламной деятельности в Internet ограничивается тем, что для оценки ее эффективности рекламодатели не могут полагаться на традиционно используемые схемы рейтингования. Скажем, в телевизионной рекламе требуются надежные и эффективные методы, обеспечивающие данные о числе посещений разными пользователями Web-страниц с рекламой. При этом нужно, чтобы на стороне Web-сервера была исключена возможность завышения размеров этих показателей, и обеспечивались средства доказательства их истинности. Авторы анализируют современные методы и показывают их ограниченность.
Предлагаемая ими схема выглядит так. Имеется три стороны: клиент (C), желающий иметь доступ к некоторым Web-страницам; Web-сервер (S), обеспечивающий доступ к этим страницам, а также специальная Web-служба, выступающая в роли аудиторского агентства (AA). C, S и AA используют общую хэш-функцию H. Для получения доступа (k раз) к желаемым страницам сайта C обращается к AA. В свою очередь, AA генерирует идентификатор К (idc), выбирает случайное значение w0 и применяет к w0 хэш-функцию H k раз, получая значение wk. После этого AA посылает C кортеж (idc, k, w0), а S — кортеж (idc, wk). S запоминает эти данные и ассоциирует с ними счетчик числа обращений Lc, инициируемый нулем. Далее C k раз обращается к соответствующим страницам Web-сайта. При i-том обращении на стороне C формируется метка вида (idc, wk-i), где wj = H(wj-1) (j = 1, ..., k). При i-том обращении S проверяет законность idc, проверяет, что wk-i+1 действительно равняется H(wk-i) и увеличивает Lc на единицу. После обработки k-того обращения S посылает AA кортеж (idc, k, w0) в качества доказательства того, что данный клиент действительно обратился к соответствующим страницам k раз. Авторы показывают, что их метод лишен недостатков ныне используемых методов и описывают реализацию прототипа в среде ОС Linux с использованием Netscape Navigator 4.76 и Apache Web Server 1.3.19.
У следующей статьи пять авторов; первым в списке указан Сантош Рангараджан (Santosh Rangarajan). Название статьи — «Кластеризация пользователей Web с использованием адаптивных нейронных сетей» (Adaptive Neural Network Clustering of Web Users). От уровня персонализации сервисов, предоставляемых пользователям Web-сайта, во многом зависит популярность сайта. В поддерживаемых Web-серверами журналах имеются содержательные данные, характеризующие паттерны доступа пользователей. Однако реструктуризация сайта с учетом индивидуальных интересов пользователей вызывает слишком большие расходы. Одно из возможных компромиссных решений состоит в выявлении групп пользователей с близкими интересами и организация структуры сайта в соответствии с потребностями разных групп. Это часть сравнительно новой области исследований, называемой Web Usage Mining. Авторы разработали алгоритм кластеризации, группирующий пользователей в соответствии с их паттернами доступа к Web-сайту. Алгоритм основан на варианте ART1 теории адаптивного резонанса. ART1 обеспечивает подход, адаптирующийся к изменениям при модификации паттернов доступа пользователей без потери ранее накопленной информации. Алгоритм применяется к двоичным векторам, строящимся на основе URL, к которым наиболее часто обращаются члены группы пользователей. Авторы утверждают, что эффективность их алгоритма превышает эффективность традиционных алгоритмов кластеризации. Кроме того, разработана схема, предсказывающая будущие запросы пользователей. Точность предсказания составила 97,78%.
Последняя статья, которую редакция журнала отнесла к тематической подборке, называется «Основанная на XML спецификация безопасности документов Web-сервисов» (XML-Based Specification for Web Services Security). Ее написали Рэфей Бхатти (Rafae Bhatti), Элиза Бертино (Elisa Bertino), Ариф Гхафур (Arif Ghafoor) и Джеймс Йоши (James Joshi). В действительности, речь идет о механизме контроля доступа к документам через Web-сервисы. Авторы развивают подход, основанный на модели RBAC (Role-Based Access Control — «контроль доступа на основе ролей»). Подход состоит в дополнении существующих механизмов обеспечения безопасности средствами спецификации политики контроля доступа. При сохранении общей семантики RBAC вводятся расширения, включающие понятия иерархии ролей и разделения ограничений режима. Спецификация доступа к контенту допускается на концептуальном уровне, а также уровнях схемы, экземпляра и элемента документа (имеется в виду, что все документы представлены на языке XML). В модели авторов при проверке правомочности доступа также учитывается контекст, в котором осуществляется попытка доступа. В общих чертах описывается основанный на XML язык спецификации политики доступа в терминах мандатов пользователей, ролей и разрешений.
Перейдем к другим статьям апрельского номера журнала. Бо Санден (Bo Sanden) представил материал «Сражение с нитями Java» (Coping with Java Threads). Эта статья является хорошим кратким введением в механизм нитей языка Java. В основном автор концентрируется на механизмах синхронизации нитей. Описывается действие механизма взаимного исключения нитей (synchronized) и механизма синхронизации по условию (wait). Рассматриваются соответствующие синтаксические конструкции. Наконец, обсуждаются типичные ситуации, в которых наиболее часто возникают ошибки синхронизации. По всей видимости, статья может быть действительно полезна для программистов, которые впервые столкнулись с параллельным программированием в среде Java.
У следующей статьи, «Извлечение знаний из данных о преступлениях: общая схема и некоторые примеры» (Crime Data Mining: A General Framework and Some Examples), опять много авторов; укажу первого в списке — это Хсинчун Чен (Hsinchun Chen). В статье представлена общая схема системы извлечения знаний из данных о преступлениях, которая разрабатывалась исследователями Аризонского университета с 1997 года в рамках проекта Coplink (ai.bpa.arizona.edu/coplink). В проекте использовались методы идентификации объектов на основе паттернов (entity extraction), выявления ассоциативных правил, предсказания, визуализации паттернов и т.д. Работа опиралась на классификационную базу данных о преступлениях полицейского управления г. Таксон. Описываются три примера реального использования системы.
Последнюю статью номера написали Нимрод Мегиддо (Nimrod Megiddo) и Дхармендра Модха (Dharmendra Modha) из исследовательского центра IBM Almaden Research Center. Статья называется «Адаптивный алгоритм замещения кэша с результатами, лучшими, чем у LRU» (Outperforming LRU with an Adaptive Replacement Cache Algorithm). Предыдущие попытки внедрения алгоритмов, обеспечивающих результаты, лучшие, чем у алгоритма LRU (Least Recently Used), не удавались по причинам больших накладных расходов и потребности в предварительной настройке. Разработанный авторами адаптивный алгоритм замещения кэша (Adaptive Replacement Cache — ARC) превосходит LRU и лишен этих недостатков. Алгоритм предполагает поддержку двух списков страниц — L1 и L2. Максимальная длина обоих списков составляет 2c, где c — размер кэша в страницах. Оба списка формируются в стиле LRU. При перемещении в кэш страницы, номер которой отсутствует в обоих списках, этот номер заносится в начало списка L1. При обращении к странице, номер которой фигурирует в одном из списков, этот номер переносится в начало списка L2. Важной особенностью алгоритма является то, что только в начале каждого из списков (подсписках T1 и T2) находятся номера страниц, находящихся в кэше, т.е. поддерживается история страниц, недавно вытесненных из кэша. Страница для замещения выбирается из конца списка — T1 или T2 в зависимости от значения параметра p, определяющего текущую допустимую длину списка T1 (а тем самым, и длину T2). Адаптивность алгоритма состоит в том, что значение p изменяется в зависимости от вида рабочей нагрузки. Приводимые результаты экспериментов убедительно доказывают преимущества ARC перед рядом других известных алгоритмов.
Тем, кто еще не вступил в IEEE Computer Society в 2004 году, напоминаю, что сейчас самое время оформить подписку на второе полугодие. Сергей Кузнецов, kuzloc@ispras.ru.
