Коллоквиум молодых исследователей по организации информации и системному программированию (CIMSP)

Пятница, 24 апреля 2015
CS центр (БЦ Таймс, Кантемировская, 2, м. Лесная)

 О коллоквиуме
Важные даты
Как стать участником



Программа работы коллоквиума

24 апреля 2015

9:45 Открытие коллоквиума
  Заседание 1а: Индексы, обработка запросов, анализ данных
  Председатель: Е.Г. Михайлова
10:00 A parallel R-tree bulk-loading algorithm with inter-thread partitioning optimization
  Ilya Shkuratov and George Chernishev

New hardware and ever-increasing problem sizes require constant development of an efficient indexing algorithms. Thus, one has not only balance a tree quality and index construction time, but also efficiently use the opportunities offered by a new hardware to handle the ever increasing data volumes. In this paper we study the parallel static R-tree construction algorithms for the shared-memory architecture. We briefly survey existing bulk-loading methods and discuss their deficiencies and strong points. Then we describe a recently proposed bulk-loading algorithm for shared-nothing architecture. After that we suggest to tailor it to shared-memory case. It can be used on shared-memory system if enough memory is provided. Furthermore, we modify this algorithm to take advantage of the shared-memory architecture, while only slightly raising the computational expenses. The modification allows to improve the overall index quality, by lowering the number of leaf accesses during window query processing.

10:20 Beacon heuristic for top-k closeness centrality problem
  Vsevolod Sevostyanov and George Chernishev

Closeness centrality is one of the popular centrality metrics which are applicable to a wide class of social network analysis problems. In this paper, we survey some of the existing algorithms for an exact and approximate evaluation of this metric. Then we describe a simple algorithm for selection of the top-k central vertices in an undirected connected graph. Our idea is the following: evaluate the sum of the shortest-path distances from some “beacon” vertices to all the other, and then, use them to estimate this value for the rest of the vertices in this connected component. Top-k vertices with the least values are the most central ones. Finally, we describe the further improvement of the heuristic.

10:40 High-level language for the algebra of fuzzy queries in a heterogeneous environment
  Nickolay Saveliev

"n the moment there are a lot of techniques to process data with great variety and volume and it becomes important to combine many of them into powerful tools. Such tools need to have expressive query language, which can be built on top of a strong algebra with great possibilities for optimization. This article defines a parameterized high-level query language to handle fuzzy queries to heterogeneous data sources and its translation to extended relational algebra. "

11:00 A query executor over heterogeneous information resources
  Aleksey Samarin

"At the present time, data processing in a heterogeneous environment is related to such issues as approximate algorithms for a query execution, subqueries transfer to different information resources and many others. There are a lot of methods for solving that kind of problems. In the current work we will consider one of the approaches to processing data from heterogeneous resources. There are three main components in the system, based on that approach. The first component is high-level declarative query language. The second component is query execution plan optimizer. And the third component is query execution engine. In this extended abstract we consider a query execution architecture for earlier mentioned system."

11:20 Эффективная детекция и локализация графического текста на видео
  Sergei Ovchinnikov

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

  Заседание 1б: Роботы
  Председатель: А. Иванов
10:00 Инструментальные средства программирования роботов на .NET/Mono
  Alexander Kirsanov and Iakov Kirilenko

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

10:20 Design of mobile robot on Raspberry Pi
  Arthur Huletski and Dmitriy Kartashov

"teel Lemon is a robot constructed with Trik toolkit and Raspberry Pi as a main controller for testing algorithms related to robotics (e.g. SLaM) on a physical device. The robot is created from scratch using affordable sensors and actuators. It has differential steering (two motors with encoders are used), sonar sensor, camera and is powered by 11.1V Li-Po battery. This document describes robot design, both hardware and software. "

10:40 Разработка языка описания пользовательских сценариев в платформе QReal
  Dmitrii Chernov and Dmitrii Mordvinov

"В настоящее время существует огромное множество программных сред с обширной функциональностью для решения различных задач. Зачастую, самостоятельное знакомство пользователей с программой приводит к нежеланию запускать ее вновь. Важным аспектом, следовательно, является обучающая инфраструктура для освоения всей функциональности среды пользователями. Работа посвящена реализации языка пользовательских сценариев в DSM-платформе QReal и применению его в качестве обучающей инфраструктуры в среде визуального программирования роботов TRIK Studio."

10:55 QoS monitoring in OpenFlow Software-Defined Networks
  Edward Ryabikov

Software-defined networks (SDN) became one of the most promising and interesting networking technologies in the past years. However, the problem of QoS monitoring in SDN is still not resolved. The current solutions have many problems such as using of active monitoring method, impossibility of assessment of control flow impact on switch performance and so on. This paper covers the common methods for network performance measurement and the solutions used for QoS evaluation in SDN. Also it briefly describes the implemented prototype of the instrument that is used for passive QoS monitoring in SDN.

11:10 Feature tracking for dynamic 3D scene reconstruction
  Kirill Kuznetsov

"3D model of surrounding area could be used for mobile SLAM (Simultaneous Localization and Mapping) robot navigation, obstacle avoidance and performing observation or manipulation tasks. 3D scene is constructed using set of frames from robot video system. In order to reconstruct 3D scene feature points, like corners, should be extracted out of video frame succession. Then they should be iteratively tracked in the video flow. 3D reconstruction requires accurate evaluation of such tracks, so feature tracking should be precise. Calculations made on robot controller, which has computational and memory resources limitations. As model being constructed and specified during process of robot movement, features should be detected and feature tracks should be evaluated in the real-time. A new approach for real-time, lightweight and precise feature tracking for 3D scene reconstruction is proposed. High-speed feature detection is combined with accurate optical flow calculation for sparse set of points. Solution configurations for best performance and longest feature tracks are estimated experimentally."

11:25 Экспериментальное исследование алгоритма оценивания положения движущейся точки
  Roman Zhukov

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

11:40 Кофе
  Заседание 2а: анализ данных
  Председатель: А.С. Ярыгина
12:00 Автоматическое выделение фаз ментальной активности
  Алина Дубатовка

"В данной работе рассматривается задача поиска фаз мозговой активности в данных частоты сердечных сокращений (ЧСС). Рассмотрены наиболее популярные подходы к обработке сигналов, выделению фаз в данных и изучению ментальных процессов. Предложена трёхступенчатая схема алгоритма, позволяющего выделять фазы ментальной активности без предварительного обучения, основываясь только на данных конкретного испытуемого, что обеспечивает учёт индивидуальных психофизиологических особенностей каждого человека. "

12:20 Обнаружение сложных стереотипов
  Светлана Китайгородская

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

12:40 Выявление аномалий магнитного поля с помощью алгоритмов кластеризации
  Елена Волжина

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

13:00 Система мониторинга продуктов питания с использованием методов машинного обучения
  Иван Муренин

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

13:15 Использование свёрточных нейронных сетей с обратным распространением ошибки для создания captcha breaker.
  Vyacheslav Busarov and Stanislav Sartasov

"В повседневной жизни многие пользователи вынуждены иметь дело с CAPTCHA (от англ. Completely Automated Public Turing test to tell Computers and Humans Apart — полностью автоматизированный публичный тест Тьюринга для различения компьютеров и людей), что доставляет множество неудобств. В связи с этим появилась актуальная проблема создания полностью автоматизированного механизма прохождения данного теста — captcha breaker, создание которого рассматривается в данной работе. Основным требованием является универсальность — независимость от конкретной разновидности CAPTCHA. За основу алгоритма взята свёрточная нейронная сеть с обратным распространением ошибки. Приводится аргументы в пользу заявленного метода, его анализ, а также обзор уже существующих решений с рассмотрением их достоинств и недостатков. В статье описывается классификация CAPTCHA, этапы работы с ними и успешное использование выбранной нейросети при решении схожей задачи. Делается вывод об оценке итоговой точности решения, обозначаются дальнейшие перспективы исследования. "

13:30 Обнаружение текста в коллекциях изображений, содержащих текст на разных языках
  Mikhail Zarechenskiy

"Обнаружение текста на изображении является одним из самых важных этапов для дальнейшего распознавания текста. Большинство существующих алгоритмов обнаружения текста разрабатывались и тестировались на текстах, содержащих английский язык. В данной работе рассматриваются известные алгоритмы обнаружения текста и исследуются на предмет инвариантности к языку."

  Заседание 2б: Роботы и верификация
  Председатель: Я.А. Кириленко
12:00 Автоматическая идентификация живописных полотен по фотографии
  Сергей Шубин

В данной работе рассматривается задача идентификации живописного полотна по его фотографии в базе музея (размер базы — порядка 10.000 записей). Задача интересна тем, что изображения для идентификации обычно сильно испорчены плохой предобработкой (обрезанием по границам полотна), некачественными фотокамерами и на изображении присутствует большое количество помех и бликов из-за защитного материала полотна, что усложняет задачу. Цель данной работы — реализовать библиотеку на C++ для идентификации изображений и изучить стабильность определения полотна при подаче реальных фотографий. В качестве системы для построения дескрипторов была выбрана связка детектора особых точек на основе Difference of Gaussian и Scale Invariant Feature Transform как дескриптора особых точек. Были проведены тесты над реальными снимками картин и показана близкая к 100% точность идентификации в рамках данной задачи.

12:20 Оптимизация нового алгоритма сжатия изображений без потерь
  Vladimir Glazachev and Rustam Azimov

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

12:35 Метод обмена данными и сохранения их целостности в децентрализованной сети автономных мобильных роботов
  Василий Калитеевский, Кирилл Тюшев and Константин Амелин

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

12:50 Разработка алгоритмов идентификации и слежения для мобильных роботов
  Vitaly Pryanechnikov

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

13:05 A User and Rights Management System for the Geo2tag LBS Platform
  Benjamin Ezepue

"One of the main problems developers of open source software projects face is how to effectively manage the large number of users that use their product. The Geo2tag open source location-based services (LBS) platform provides developers with an efficient environment for prototyping and developing LBS products. As the platform grows, managing the huge number of potential users and appropriately assigning rights to platform resources will be a problem. In this paper we propose a user and rights management system for the Geo2tag LBS platform. An analysis of existing popular user management systems was made. We found out that none of them fully met our functional requirements for managing users and rights to platform resources. We developed our own user and rights management system by improving on the Userfrosting user management system. HybridAuth was used to provide OAuth support. "

13:20 Разработка модуля инструментальной среды для обнаружения сигнатурных дефектов в программном обеспечении
  "Рудольф Зайцев and Владимир Ицыксон "

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

13:35 Верификация диаграмм по методу Model Checking в TRIK Studio
  Дмитрий Копытов and Дмитрий Мордвинов

"TRIK Studio - среда визуального программирования роботов. Графические программы, как и текстовые, имеют ошибки, особенно если это параллельные, распределённые или многопоточные программы. Некоторые ошибки, проявляющиеся в редких ситуациях, обычно невозможно обнаружить тестированием. Зачастую такие ошибки можно выявить с помощью различных методов автоматизированной верификации программного кода. В связи с этим появилась необходимость внедрения в среду TRIK Studio инструмента для верификации графических программ."

14:00 Обед
  Заседание 3а:обработка изображений
  Председатель: Н.Г. Графеева
15:00 Создание алгоритма детектирования объектов на основе разномасштабных haar-классификаторов
  Павел Русинов

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

15:20 Learning city scene structure from a single image
  Dmitrii Petukhov

We consider the problem of understanding an image scene structure. Specifically, we limit our scope with outdoor images which have been made in a city environment. Our main goal is to come up with an algorithm which is solving the problem by labeling parts of an image into coarse geometric classes as “sky”, “vertical” and “ground”. In this paper, we present an outline of such an algorithm.

15:40 Робот “Глухарь” (Акустическая сенсорика, определение направления звука)
  Nikolai Karulin

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

  Заседание 3б: Системы хранения
  Председатель: Г.А. Чернышев
15:00 Implementation of VENUS Protocol for Cloud Object Storage Testing
  Sergey Morozov

"A cloud object storage system, like any distributed computer system, cannot simultaneously provide consistency, availability and partition-tolerance guaranties. Cloud storage providers have to choose between availability and consistency since partition-tolerance is extremely important for geo-distributed cloud storage systems. A lot of scientific research has been devoted to data consistency problem in distributed computer systems. One of them is a VENUS - protocol that guaranties integrity and casual consistency of data for applications accessing cloud object storage without requiring trusted components and any modification to the storage. This paper proposes some modifications in the VENUS protocol with an emphasis on the use of it in a cloud object storage testing with a group of workload generators working in accordance with Amazon S3 protocol. It also describes the implementation of VENUS protocol that does not require modification of existing S3 applications and workload generators."

15:20 Реализация виртуальной файловой системы для ОС Embox
  Denis Deryugin

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

15:40 Мультинодный кластер
  Евгений Анастасиев

"В распределенной системе хранения данных отказ узла является критичной ситуацией. В текущей архитектуре двухконтроллерной системы хранения данных RAIDIX описанная проблема решается следующим образом: сервер объектного хранения (OSS) переносится с отказавшего узла на оставшийся сервер. Это влечет за собой потерю половины вычислительных ресурсов и интерфейсов и, как следствие, ограничение производительности СХД. Возникает задача создания многоузлового кластера хранения, в котором нагрузка распределялась бы равномерно по множеству узлов, и отказ одного не становился бы критичной ситуацией. Соответственно, разработка алгоритма функционирования многоузлового кластера хранения является актуальной задачей. В данной статье приводится оптимальный алгоритм распределения ресурсов хранения по узлам кластера. Предложенный алгоритм допускает возможность отказа произвольного набора узлов кластера при условии, что узлы имеют достаточную мощность, а также хотя бы один узел остаётся работоспособным. Как результат, отказоустойчивость кластера хранения повышается в несколько раз по сравнению с состоянием текущей его реализации. Оптимизация распределения ресурсов по узлам состоит в том, что для восстановления штатного режима работы кластера требуется минимальное количество переносов активных ресурсов хранения при отказе любого из узлов. Представленный в статье алгоритм функционирования кластера в дальнейшем предполагается использовать в последующих реализациях распределенной СХД RAIDIX."

16:00 Оптимизация операций восстановления данных в СХД, использующих помехоустойчивое кодирование
  Valeria Zaibert

"Системы хранения данных (СХД) являются одним из самых распространенных сервисов, использующихся в сегодняшнем мире IT. Для построения масштабируемых распределенных отказоустойчивых хранилищ в последнее время все чаще используют помехоустойчивое кодирование. При этом, многие системы основаны на решениях с открытым исходным кодом. Один из подходов в помехоустойчивом кодировании - использование систематических кодов Рида-Соломона. Информация, записываемая на СХД, разбивается на отдельные информационные блоки. Затем выполняется расчёт различных контрольных сумм (кодирование). Каждая контрольная сумма сохраняется в отдельный проверочный блок и используется затем для восстановления данных (декодирования). Для расчета контрольных сумм и восстановления данных производится операция умножения матрицы кодирования или декодирования на вектора с данными. При этом, скорость кодирования сильно влияет на скорость записи в СХД, а скорость декодирования — на скорость чтения. В ходе исследовательской работы мы изучили несколько открытых библиотек, реализующих помехоустойчивое кодирования, описанное выше, и провели сравнение их производительности. В их числе: FECpp, Holostor, Zfec, Jerasure и ISA-L (Intel). Выяснилось, что одно из узких мест при восстановлении данных, это построение матрицы декодирования. Нами предложена реализация алгоритма обращения матрицы методом Жордана-Гаусса с использованием векторных операций SSE. Предложенная векторная реализации заметно быстрее аналогов из открытых библиотек. Например, мы добились увеличения скорости декодирования при использовании нашего метода совместно с библиотекой ISA-L минимум в три раза."

16.20 Закрытие коллоквиума