Logo    
Деловая газета CitCity.ru CITKIT.ru - все об Open Source Форумы Все публикации Учебный центр Курилка
CitForum    CITForum на CD    Подписка на новости портала Море(!) аналитической информации! :: CITFORUM.RU
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

17.01.2017

Google
WWW CITForum.ru
С Новым годом!
2004 г.

Алгоритм LRU наконец-то превзойден

Сергей Кузнецов

Обзор апрельского, 2004 г. номера журнала Computer (IEEE Computer Society, V. 37, No 4, April 2004)

Авторская редакция.
Также обзор опубликован в журнале "Открытые системы", #05/2004

На обложке журнала тема апрельского номера обозначена как "Putting the Web to Work" (что-то вроде "Приведения Web в действие"). В действительности с Web связаны только три из шести больших статей, и тематика этих трех статей очень неоднородна. Тем не менее, начнем обзор именно с них.

Первая статья называется "Инфраструктура программного обеспечения для аутентифицируемого снятия показаний в Web" ("A Software Infrastructure for Authenticated Web Metering"). Авторы статьи - Карло Блундо и Стельвио Кимато (Carlo Blundo, Stelvio Cimato, carblu|cimato@dia.unisa.it, University of Salerno). Объем рекламы, размещаемой на Web-сайтах, постоянно растет. По данным Бюро интерактивной рекламы (Interactive Advertising Bureau) в последние 6 месяцев 2002 г. на Internet-рекламу в США было истрачено почти 3 миллиарда долларов. Развитие рекламной деятельности в Internet ограничивается тем, что в этом случае рекламодатели не могут полагаться на схемы оценки рейтингов, которые традиционно используются, например, в телевизионной рекламе. Требуются надежные и эффективные методы, обеспечивающих данные о числе посещений разными пользователями Web-страниц, на которых размещена реклама. При этом нужно, чтобы на стороне Web-сервера была исключена возможность завышения размеров этих показателей и обеспечивалось средства доказательства их истинности. Авторы анализируют методы, используемые в настоящее время, и показывают их ограниченность. Предлагаемая схема выглядит следующим образом. В ней участвуют три стороны: клиент (C), желающий иметь доступ к некоторым Web-страницам; Web-сервер (S), обеспечивающий доступ к этим страницам и специальная Web-служба, аудиторское агентство (AA). C, S и AA используют общую хэш-функцию H. Для получения доступа (k раз) к желаемым страницам Web-сайта (регистрации) 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 K. Rangarajan, , santosh_kumarr@hotmail.com, Louisiana Tech. University). Название статьи - "Кластеризация пользователей Web с использованием адаптивных нейронных сетей" ("Adaptive Neural Network Clustering of Web Users"). От уровня персонализации сервисов, предоставляемых пользователям Web-сайта, во многом зависит популярность сайта. В поддерживаемых Web-серверами журналах имеются содержательные данные, характеризующие паттерны доступа пользователей. Однако реструктуризация сайта с учетом индивидуальных интересов пользователей вызывает слишком большие расходы. Одно из возможных компромиссных решений состоит в выявлении групп пользователей с близкими интересами и организация структуры сайта в соответствии с потребностями разных групп. Это часть сравнительно новой области исследований, называемой Web Usage Mining. Авторы разработали алгоритм кластеризации, группирующий пользователей в соответствии с их паттернами доступа к Web-сайту. Алгоритм основан на варианте ART1 теории адаптивного резонанса (adaptive resonance theory, см. www.cs.brandeis.edu/~cs113/docs/other/heins_tauritz.pdf). ART1 обеспечивает подход, адаптирующийся к изменениям в изменении паттернов доступа пользователей без потери ранее накопленной информации. Алгоритм применяется к двоичным векторам, строящимся на основе URL, к которым наиболее часто обращаются члены группы пользователей. Авторы утверждают, что эффективность их алгоритма превышает эффективность традиционных алгоритмов кластеризации. Кроме того, разработана схема, предсказывающая будущие запросы пользователей. Точность предсказания составила 97,78%.

Последняя статья, которую редакция журнала Computer отнесла к тематической подборке, называется "Основанная на XML спецификация безопасности документов Web-сервисов" ("XML-Based Specification for Web Services Security"). Статью написали Рэфей Бхатти, Элиза Бертино, Ариф Гхафур (Rafae Bhatti, rafae@purdue.edu, Elisa Bertino, bertino@cs.purdue.edu, Arif Ghafoor, ghafoor@ecn.purdue.edu) и Джеймс Йоши (James B.D. Joshi, jjoshi@mail.sis.pitt.edu, University of Pittsburgh). Название статьи не вполне точно отражает ее содержание. На самом деле, речь идет о механизме контроля доступа к документам, доступ к которым осуществляется через Web-сервисы. Авторы развивают подход, основанный на модели RBAC (Role-Based Access Control - контроль доступа на основе ролей). Подход авторов состоит в дополнении существующих механизмов обеспечения безопасности средствами спецификации политики контроля доступа. При сохранении общей семантики RBAC вводятся расширения, включающие понятия иерархии ролей и разделения ограничений режима. Спецификация доступа к контенту допускается на концептуальном уровне, а также уровнях схемы, экземпляра и элемента документа (имеется в виду, что все документы представлены на языке XML). В модели авторов при проверке правомочности доступа также учитывается контект, к котором осуществляется попытка доступа. В общих чертах описывается основанный на XML язык спецификации политики доступа в терминах мандатов пользователей, ролей и разрешений. В заключение статьи обсуждается общая архитектура программного обеспечения, основанного на предложенной модели. Отмечается наличие опытной реализации.

Перейдем к другим статьям апрельского номера журнала. Бо Санден (Bo Sanden, bsanden@acm.org, Colorado Technical University) представил статью "Сражение с нитями Java" ("Coping with Java Threads"). Эта статья является хорошим кратким введением в механизм нитей языка Java. В основном автор концентрируется на механизмах синхронизации нитей. Описывается действие механизма взаимного исключения нитей (synchronized) и механизма синхронизации по условию (wait). Рассматриваются соответствующие синтаксические конструкции. Наконец, обсуждаются типичные ситуации, в которых наиболее часто возникают ошибки синхронизации. Наверное, эта статья может быть действительно полезна для программистов, которые впервые столкнулись с параллельным именно в среде Java.

У следующей статьи - "Извлечение знаний из данных о преступлениях: общий каркас и некоторые примеры" (Crime Data Mining: A General Framework and Some Examples" - опять много авторов (пять). Поэтому мы снова укажем только первого в списке - это Хсинчун Чен (Hsinchun Chen, hchen@eller.arizona.edu, University of Arizona). В статье представлена общая схема системы извлечения знаний из данных о преступлениях, которая разрабатывалась исследователями Аризонского университета в проекте Coplink с 1997 г. (http://ai.bpa.arizona.edu/coplink). В проекте использовались методы идентификации объектов на основе паттернов (entity extraction), выявления ассоциативных правил, предсказания, визуализации паттернов и т.д. Работа опиралась на классификационную базу данных о преступлениях полицейского управления г. Таксон. Описываются три примера реального использования системы.

Последнюю статью этого номера написали Нимрод Мегиддо и Дхармендра Модха (Nimrod Megiddo, Dharmendra S. Modha, megiddo|dmodha@almaden.ibm.com, 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

Подписка на новости IT-портала CITForum.ru
(библиотека, CITKIT.ru, CitCity)

Новые публикации:

24 декабря

CITKIT.ru:

  • Новогодние поздравления
  • Сергей Кузнецов. Цикл Операционные системы: Ностальгия по будущему:

  • Алексей Федорчук. OpenSolaris 2008.11 Release

  • Сергей Голубев:

  • Евгений Чайкин aka StraNNik (Блогометки):

    17 декабря

  • С.Д.Кузнецов. Базы данных. Вводный курс

    10 декабря

    CITKIT.ru:

  • OpenSolaris 2008.11 Release

  • Альтернативные ОС: две грустные истории (С.Кузнецов)
  • Nokia N810 — доведение до ума
  • CitCity:

  • Платформа 2009: заоблачные перспективы Microsoft

    4 декабря

  • Лекция С.Д.Кузнецова Понятие модели данных. Обзор разновидностей моделей данных

    CITKIT.ru:

  • OpenSolaris 2008.11 Release. Первые впечатления

  • Linux vs FreeBSD: продолжим "Священные войны"?

  • Nokia N810 as is

  • Индульгенция для FOSS

  • Друзья СПО'2008

    26 ноября

  • Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

    CitCity:

    CITKIT.ru:

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • 19 ноября

  • Проблемы экономики производства крупных программных продуктов

  • Язык модификации данных формата XML функциональными методами

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Заметки к книге:

  • FreeBSD: монтирование сменных устройств и механизм HAL
  • Текстовый редактор ee

    12 ноября

  • Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила (Гоц Грейф, перевод: Сергей Кузнецов)

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:
  • OSS в России: взгляд правоведа (В.Житомирский)

  • Новая статья из цикла С.Голубева "Железный марш":

    29 октября

  • О некоторых задачах обратной инженерии

  • Веб-сервисы и Ruby

  • Тестирование web-приложений с помощью Ruby

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

  • PuppyRus Linux - беседа с разработчиком (С.Голубев)

  • Сергей Кузнецов. Заметка не про Linux

    22 октября

  • Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки

    CITKIT.ru:

  • Сергей Кузнецов. Почему я равнодушен к Linux

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • Что надо иметь
    3. Базовые познания

    CitCity:

  • Управление IT-инфраструктурой на основе продуктов Microsoft

    15 октября

  • Методы бикластеризации для анализа интернет-данных

    CitCity:

  • Разъемы на ноутбуках: что они дают и зачем их так много?
  • AMD Puma и Intel Centrino 2: кто лучше?

    CITKIT.ru:

  • Новый цикл статей С.Голубева
    Железный марш:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    8 октября

  • Автоматизация тестирования web-приложений, основанных на скриптовых языках
  • Опыт применения технологии Azov для тестирования библиотеки Qt3

    Обзоры журнала Computer:

  • SOA с гарантией качества
  • Пикоджоуль ватт бережет
  • ICT и всемирное развитие

    CitCity:

  • Пиррова победа корпорации Microsoft

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Статья из архива:

  • Я живу в FreeBSD (Вадим Колонцов)

    Новые Блогометки:

  • Перекройка шаблона Blogger или N шагов к настоящему
  • Blogger. Comment style
  • Screenie или глянцевый снимок экрана

    2 октября

    CITKIT.ru:

  • Сага о FreeBSD (А. Федорчук)

    Zenwalk: пакет недели

  • Банинг — интеллектуальное развлечение (С.Голубев)

    CitCity:

    25 сентября

  • Клермонтский отчет об исследованиях в области баз данных

    CITKIT.ru:

  • Пользователям просьба не беспокоиться... (В.Попов)

  • Снова про ZFS: диск хорошо, а два лучше
  • Командная оболочка tcsh (А.Федорчук)

    Zenwalk: пакет недели

    17 сентября

  • T2C: технология автоматизированной разработки тестов базовой функциональности программных интерфейсов
  • Технология Azov автоматизации массового создания тестов работоспособности

    CITKIT.ru:

  • FreeBSD: ZFS vs UFS, и обе-две — против всех (А.Федорчук)

    Zenwalk: пакет недели

  • Дачнет — практика без теории (С.Голубев)

    10 сентября

  • За чем следить и чем управлять при работе приложений с Oracle
  • Планировщик заданий в Oracle
    (В.Пржиялковский)

    CITKIT.ru:

  • Microsoft: ответный "боян" (С.Голубев)

  • Причуды симбиоза, или снова "сделай сам" (В.Попов)

  • Файловые системы современного Linux'а: последнее тестирование
  • Zsh. Введение и обзор возможностей
    (А.Федорчук)

    Описания пакетов Zenwalk: Zsh, Thunar, Thunar-bulk-rename, Xfce4-places-plugin, Xfce4-fsguard-plugin

    Блогометки:

  • Google Chrome
  • Лончер для ASUS Eee PC 701

    3 сентября

    CITKIT.ru:

  • Заметки о ядре (А.Федорчук):

    Добавлены описания пакетов Zenwalk: Galculator, Screenshot, Gnumeric, Pidgin

    В дискуссинном клубе:

  • И еще о Википедии и Google Knol

  • Лекция для начинающего линуксоида (С.Голубев)

    26 августа

  • Транзакционная память (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Открыт новый проект Zenwalk: пакет недели

  • Статья Текстовые процессоры и их быстродействие: конец еще одной легенды?

    21 августа

    CITKIT.ru:

  • Почему школам следует использовать только свободные программы (Ричард Столлман)
  • Беседа Сергея Голубева с учителем В.В.Михайловым

  • Википедия или Гуглезнание? Приглашение к обсуждению (Алексей Федорчук)
  • Народная энциклопедия от Google (StraNNik)

  • Обзор Mandriva 2009.0 Beta 1 Thornicrofti
  • Новичок в Линукс: Оптимизируем Mandriva 2008.1

  • Книга Zenwalk. Приобщение к Linux:

    13 августа

    CitCity:

  • Мирный Atom на службе человеку. Обзор платы Intel D945GCLF с интегрированным процессором
  • Обзор процессоров Intel Atom 230 на ядре Diamondville

  • iPhone - год спустя. Скоро и в России?

    CITKIT.ru:

  • Интермедия 3.4. GRUB: установка и настройка (из книги Zenwalk. Приобщение к Linux)

    6 августа

  • СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности? (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Интермедия 2.2. Что неплохо знать для начала (из книги Zenwalk. Приобщение к Linux)

  • И снова про шрифты в Иксах (А.Федорчук)

  • 20 самых быстрых и простых оконных менеджеров для Linux

  • Дело о трех миллиардах (С.Голубев)

    30 июля

  • OLTP в Зазеркалье (Пересказ: С. Кузнецов)

    CitCity:

  • Будущее BI в облаках?
  • Тиражные приложения и заказная разработка. Преимущества для заказчика
  • Дискуссия со сторонниками заказной разработки

    CITKIT.ru:

  • Новые главы книги Zenwalk. Приобщение к Linux:
  • Глава 8. Пакеты: средства установки, системы управления, системы построения
  • Глава 9. Zenwalk: репозитории, пакеты, методы установки

    23 июля

    CITKIT.ru:

  • Все против всех. 64 vs 32, Intel vs AMD, tmpfs vs ext3
  • Две головы от Intel

  • Zenwalk: обзор штатных приложений (глава из книги "Zenwalk. Приобщение к Linux")

  • Нормально, Григорий...

    16 июля

    Обзоры журнала Computer:

  • Перспективы и проблемы программной инженерии в XXI веке
  • Большие хлопоты с большими объемами данных
  • Перспективы наноэлектроники

    CITKIT.ru:

  • Интермедия о лицензиях (А.Федорчук. "Zenwalk. Приобщение к Linux")

  • Есть ли будущее у KDE?

  • Linux в школе: альтернативный вариант в задачах

  • Шифр (приключения агента Никодима)

    10 июля

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия вступительная. Linux или GNU/Linux? Как вас теперь называть?
  • Глава 5. Среда Xfce
  • Глава 6. Xfce: приложения и плагины

  • ZUR (Zenwalk User Repository) FAQ

    2 июля

  • Персистентность данных в объектно-ориентированных приложениях (С. Кузнецов)

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия 1.2. Дорога к Zenwalk'у. Период бури и натиска
  • Интермедия 3.3. Немного о Linux'е и "железе"
  • Глава 4. Настройка: инструментами и руками
  • Интермедия 4.1. Zenpanel и конфиги: поиски корреляции

  • Интервью с Жан-Филиппом Гийоменом, создателем дистрибутива Zenwalk

  • Linux в школе: первые итоги (С. Голубев)

    25 июня

    CITKIT.ru:

  • Zenwalk. Приобщение к Linux (А. Федорчук)

  • Логика и риторика (С.Голубев)

  • Технология Tru64 AdvFS

  • Ханс Райзер предлагает отвести полицейских к телу Нины

    18 июня

  • Проекты по управлению данными в Google (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • ОС и поддержка "железа": мифы и реальность (А. Федорчук)

  • Linux в школе: другие дистрибутивы

  • Пинок (С. Голубев)

    4 июня

  • Ландшафт области управления данными: аналитический обзор (С. Кузнецов)

    CITKIT.ru:

  • Linux в школе: слово заинтересованным лицам

  • SlackBuild: пакеты своими руками

  • Linux от компании Novell. Установка и обзор openSUSE Linux

    Все публикации >>>




  • IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей Пресс-релизы — pr@citcity.ru
    Послать комментарий
    Информация для авторов
    Rambler's Top100 This Web server launched on February 24, 1997
    Copyright © 1997-2017 CIT, © 2001-2017 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...