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

Научный семинар Института системного программирования РАН

Для получения зачета все студенты должны отчитаться за пропущенные семинары. Зачет будет проходить вместе с защитами курсовых. Расписание защит смотрите в соответствующем разделе.

Таблица посещаемости (pdf)

В докладе рассказывается о строковых B-деревьях. String B-tree представляет собой структуру для хранения текстовых данных во внешней памяти: это комбинация B-дерева и бора Патриции для индексации внутренних узлов. Рассмотрено сравнение эффективности использования строкового B-дерева по сравнению с B+-деревом. В эксперименте, описанном в статье показано, что строковые B-деревя дают значительное преимущество по сравнению с другими B-деревьями засчет уменьшения количества обращений к диску.

Докладчик:  Пастухов Роман

Материалы:

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

Доклад посвящен методу автоматического обогащения текста поясняющими ссылками на Википедию. Рассмотрены основные части алгоритма: выделение ключевых слов и создание из них ссылок на
соответствующие по смыслу статьи энциклопедии. Разбираются отличия от предыдущих подходов и освещаются возможные области применения метода.

Докдадчик: Рябов Сергей

Материалы:

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

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

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

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

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

Материалы:

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

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

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

Материалы:

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

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

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

Материалы:

Отменен

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

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

Материалы:

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

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

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

Материалы:

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

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

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

Материалы:

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

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

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

Материалы:

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