Управление данными и информационные системы

Научный семинар отдела Информационных систем Института системного программирования им. В.П. Иванникова РАН

Archive for the ‘Аннотации’ Category

Использование префиксных деревьев для организации индексов баз данных (13.04.10)

Префиксные деревья (tries) и их разновидности являются одними из самых эффективных структур данных для хренения ассоциативных массивов (обычно со строковыми ключами). Некоторые реализации префиксных деревьев (HAT-trie) сравнимы по производительности с хэш-таблицами.
При этом, в отличие от хэш-таблиц, они позволяют поддерживать отношение порядка между ключами, а также быстро получать все ключи по заданному префиксу.

Предлагается реализация разновидности префиксных деревьев для поддержки индексов баз данных в качестве альтернативы B-деревьям. Наиболее похожим типом деревьев является HAT-trie (cache-conscious trie). В данном типе деревьев учитываются особенности хренения данных в СУБД: изменения локальны относительно страниц; используется максимально компактное представление узлов (с целью занять наименьшее количество страниц). Кроме того, в отличие от B-деревьев, в продложенной структуре данных нет ограничений на длину ключа. Основная задача, которая была решена в ходе работы — это разработка эффективного алгоритма разделения страниц (splitting). Этот алгоритм позволяет обеспечивать оптимальное заполнение страниц.

В настоящее время выполняется сравнение прототипной реализации с существующими реализациями B-деревьев, в том числе, с B-деревьями, во внутренних страницах которых данные представлены в виде префиксного дерева.

Докдадчик: Борисенко Олег.

Материалы:

Презентация с семинара (pdf)

Boosting — Усиление простых классификаторов (06.04.10)

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

Докладчик: Пироженко Александр.

Материалы:

Презентация с семинара (pdf)

Методы обогащения текстовых коллекций ссылками (30.03.10)

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

Докладчик: Рязанцев Дмитрий.

Материалы:

Отменен

Алгоритмы вытеснения страниц баз данных из буферов основной памяти (23.03.10)

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

Докладчик: Сиващенко Дмитрий.

Материалы:

Презентация с семинара (pdf)

Методы сжатия веб-графа (16.03.10)

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

Докладчик: Бартунов Сергей.

Материалы:

Презентация с семинара (pdf)

Методы поиска и классификации именованных сущностей (NERC) — 09.03.10

В докладе делается обзор  исследований в области поиска и классификации именованных сущностей (Named entity recognition and classification) за последние 14 лет, от эвристик и созданных вручную правил  до методов машинного обучения. Кратко рассказано об использующихся методах оценки точности и полноты алгоритмов. В заключении  рассматривается система Nymble, основанная на HMM.

докладчик: Сильвестров Алексей.

Материалы:

Презентация с семинара (ppt)

Модель Conditional Random Fields (02.03.10)

Доклад посвящен статистической модели Conditional Random Fields (CRF), наиболее часто используемой в приложениях связанных с  обработкой. Во введении делается краткий обзор и сравнение методов машинного обучения, используемых для классификации: наивный байесовский классификатор; метод максимальной энтропии (метод логистической регрессии); скрытая марковская модель. Далее подробно рассматриваются модели Linear-chain CRF и Conditional Random Fields, предлагаются методы оценки параметров моделей, в том числе с учетом проблемы переобучения. В заключении обсуждаются актуальные приложения CRF.

Докладчик: Астраханцев Никита.

Материалы:

Презентация с семинара (pdf)