Параллельный алгоритм поиска и идентификации подобных информационных структур
Предложен параллельный алгоритм поиска и идентификации подобных информационных структур. Этот алгоритм может применяться для фильтрации эквивалентных информационных структур и выборки данных по шаблону. Выполнена оценка вычислительной сложности, а также изложены результаты тестирования последователь...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2015 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/168360 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Параллельный алгоритм поиска и идентификации подобных информационных структур / А.П. Сергеев // Компьютерная математика. — 2015. — № 1. — С. 50-56. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-168360 |
|---|---|
| record_format |
dspace |
| spelling |
Сергеев, А.П. 2020-04-30T17:15:10Z 2020-04-30T17:15:10Z 2015 Параллельный алгоритм поиска и идентификации подобных информационных структур / А.П. Сергеев // Компьютерная математика. — 2015. — № 1. — С. 50-56. — Бібліогр.: 5 назв. — рос. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168360 004.75 Предложен параллельный алгоритм поиска и идентификации подобных информационных структур. Этот алгоритм может применяться для фильтрации эквивалентных информационных структур и выборки данных по шаблону. Выполнена оценка вычислительной сложности, а также изложены результаты тестирования последовательной и параллельной версий алгоритма. Приведены практические примеры использования алгоритма в компьютерной химии. Запропоновано паралельний алгоритм пошуку та ідентифікації подібних інформаційних структур. За допомогою цього алгоритму можна фільтрувати еквівалентні інформаційні структури та виконувати вибірку даних на базі обраного шаблону. Виконано оцінку обчислювальної складності алгоритму, а також проведене тестування послідовної та паралельної версій алгоритму. Наведене практичне застосування алгоритму у компь’ютерній хімії. The paper gives an overview of parallel algorithm for searching and identification of similar information structures. This algorithm can be applied to filter the equivalent information structures and retrieving data in a predetermined pattern. The evaluation of the computational complexity is given and results of the test series and parallel version of the algorithm are presented. The application of the algorithm in computational chemistry is described. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Инструментальные средства информационных технологий Параллельный алгоритм поиска и идентификации подобных информационных структур Паралельний алгоритм пошуку та ідентифікації подібних інформаційних структур Parallel algorithm for search and identification of similar information structures Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Параллельный алгоритм поиска и идентификации подобных информационных структур |
| spellingShingle |
Параллельный алгоритм поиска и идентификации подобных информационных структур Сергеев, А.П. Инструментальные средства информационных технологий |
| title_short |
Параллельный алгоритм поиска и идентификации подобных информационных структур |
| title_full |
Параллельный алгоритм поиска и идентификации подобных информационных структур |
| title_fullStr |
Параллельный алгоритм поиска и идентификации подобных информационных структур |
| title_full_unstemmed |
Параллельный алгоритм поиска и идентификации подобных информационных структур |
| title_sort |
параллельный алгоритм поиска и идентификации подобных информационных структур |
| author |
Сергеев, А.П. |
| author_facet |
Сергеев, А.П. |
| topic |
Инструментальные средства информационных технологий |
| topic_facet |
Инструментальные средства информационных технологий |
| publishDate |
2015 |
| language |
Russian |
| container_title |
Компьютерная математика |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Паралельний алгоритм пошуку та ідентифікації подібних інформаційних структур Parallel algorithm for search and identification of similar information structures |
| description |
Предложен параллельный алгоритм поиска и идентификации подобных информационных структур. Этот алгоритм может применяться для фильтрации эквивалентных информационных структур и выборки данных по шаблону. Выполнена оценка вычислительной сложности, а также изложены результаты тестирования последовательной и параллельной версий алгоритма. Приведены практические примеры использования алгоритма в компьютерной химии.
Запропоновано паралельний алгоритм пошуку та ідентифікації подібних інформаційних структур. За допомогою цього алгоритму можна фільтрувати еквівалентні інформаційні структури та виконувати вибірку даних на базі обраного шаблону. Виконано оцінку обчислювальної складності алгоритму, а також проведене тестування послідовної та паралельної версій алгоритму. Наведене практичне застосування алгоритму у компь’ютерній хімії.
The paper gives an overview of parallel algorithm for searching and identification of similar information structures. This algorithm can be applied to filter the equivalent information structures and retrieving data in a predetermined pattern. The evaluation of the computational complexity is given and results of the test series and parallel version of the algorithm are presented. The application of the algorithm in computational chemistry is described.
|
| issn |
2616-938Х |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/168360 |
| citation_txt |
Параллельный алгоритм поиска и идентификации подобных информационных структур / А.П. Сергеев // Компьютерная математика. — 2015. — № 1. — С. 50-56. — Бібліогр.: 5 назв. — рос. |
| work_keys_str_mv |
AT sergeevap parallelʹnyialgoritmpoiskaiidentifikaciipodobnyhinformacionnyhstruktur AT sergeevap paralelʹniialgoritmpošukutaídentifíkacíípodíbnihínformacíinihstruktur AT sergeevap parallelalgorithmforsearchandidentificationofsimilarinformationstructures |
| first_indexed |
2025-11-26T16:45:18Z |
| last_indexed |
2025-11-26T16:45:18Z |
| _version_ |
1850628849065263104 |
| fulltext |
50 Компьютерная математика. 2015, № 1
Предложен параллельный алго-
ритм поиска и идентификации
подобных информационных струк-
тур. Этот алгоритм может
применяться для фильтрации
эквивалентных информационных
структур и выборки данных по
шаблону. Выполнена оценка вы-
числительной сложности, а так-
же изложены результаты тес-
тирования последовательной и
параллельной версий алгоритма.
Приведены практические приме-
ры использования алгоритма в
компьютерной химии.
© А.П. Сергеев, 2015
УДК 004.75
А.П. СЕРГЕЕВ
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ПОИСКА
И ИДЕНТИФИКАЦИИ ПОДОБНЫХ
ИНФОРМАЦИОННЫХ СТРУКТУР
Введение. В работах [1, 2] описан парал-
лельный алгоритм идентификации подобных
химических соединений, а также приведена
оценка его вычислительной сложности.
Предлагается усовершенствованная версия
этого алгоритма, обладающая следующими
преимуществами:
увеличено количество характеристиче-
ских признаков, применяемых для иденти-
фикации подобных структур;
улучшена реализация параллелизма, по-
зволившая уменьшить задержки при обмене
данными между параллельными потоками,
что в свою очередь, привело к ускорению
работы алгоритма;
увеличено количество потоков и пре-
дельные размерности матриц смежности, об-
рабатываемых алгоритмом;
повышена степень универсальности ал-
горитма.
С помощью алгоритма идентифицируются
подобные информационные структуры. Раз-
работка методик, применяемых для обработ-
ки этих структур, имеет большое прикладное
значение.
В качестве информационных структур мо-
гут применяться графы, применяемые для
моделирования разных объектов. Например,
неориентированные графы используются
для моделирования молекул химических со-
единений, а деревья – для представления
XSD-схем [3].
Описание алгоритма. В качестве вход-
ных данных используются неориентирован-
ные графы, представленные матрицами
смежности. Работа алгоритма основана на
следующих утверждениях.
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ПОИСКА И ИДЕНТИФИКАЦИИ ...
Компьютерная математика. 2015, № 1 51
Определение. Между подобными информационными структурами сущест-
вует эквивалентное преобразование.
Утверждение 1. Изоморфизм графов эквивалентен подобию информацион-
ных структур.
Справедливость этого утверждения вытекает из определения изоморфных
графов и подобных информационных структур. Следовательно, проверка на на-
личие подобия информационных структур сводится к установлению факта изо-
морфизма представляющих эти структуры графов.
Определение. Инвариант изоморфизма – это свойство графа, которое сохра-
няется при выполнении изоморфных преобразований.
Благодаря использованию системы инвариантов изоморфизма ускоряется
работа алгоритма, а также уменьшаются требования к используемым вычисли-
тельным ресурсам.
Блок-схема алгоритма показана на рис. 1.
РИС. 1. Блок-схема алгоритма поиска и идентификации подобных информационных структур
Для идентификации подобия информационных структур алгоритм устанав-
ливает факт изоморфизма соответствующих графов. Если графы изоморфны
(соответствующие матрицы смежности равны с точностью до перестановок
строк и столбцов), то информационные структуры будут подобными. Данный
алгоритм включает такие модули.
А.П. СЕРГЕЕВ
52 Компьютерная математика. 2015, № 1
Модуль 1. Создание системы инвариантов изоморфизма и проверка их ра-
венства. Для каждой матрицы смежности, представляющей информационную
структуру, создается система инвариантов изоморфизма. Эта система включает
компоненты, включающие количество вершин графа (размерность матрицы
смежности), число ребер графа (уменьшенное в два раза количество ненулевых
элементов матрицы смежности), последовательность степеней вершин графа и
количество компонент связности. Степень i-й вершины графа вычисляется как
сумма ненулевых элементов, находящихся в i-й строке и в i-м столбце матрицы
смежности. По сравнению с [2], количество проверяемых инвариантов изомор-
физма увеличено до 4. Если хотя бы один из инвариантов изоморфизма первой
информационной структуры не совпадает с соответствующим инвариантом изо-
морфизма второй структуры, это означает, что информационные структуры не
изоморфны, т. е. не являются подобными. Если же инварианты изоморфизма
равны, соответствующие информационные структуры могут быть изоморфны-
ми. Для проверки изоморфизма в этом случае используется модуль 2.
Модуль 2. Оптимизированный параллельный алгоритм Ульмана. Данный
модуль выполняет непосредственную проверку информационных структур на
изоморфизм и основан на алгоритме Ульмана [4]. Для изоморфных информаци-
онных структур должно выполняться равенство
,TA PBP (1)
где A и B – матрицы смежности информационных структур, P – матрица пе-
рестановок, TP – транспонированная матрица перестановок.
В данном случае используется реализация классического алгоритма Ульма-
на [4]. На вход алгоритма поступают квадратные матрицы A и B размерности
,n n ,m n представляющие сравниваемые информационные структуры. После
завершения выполнения алгоритма генерируется матрица перестановок ,P
для которой выполняется равенство (1), а логической переменной res при-
сваивается значение true или false (в зависимости от результата выполнения
алгоритма).
Пусть )( ijpP элементы матрицы перестановок, принимающие значения
0 или 1. Для генерирования матриц перестановок и проверки справедливости
равенства (1) используется процедура ( , , ).CHECKISO A B res
Если выполняется равенство (1), это означает, что матрицы A и ,B пред-
ставляющие информационные структуры, изоморфны, а процесс генерирования
матриц перестановок завершается. В наихудшем случае (при совпадении инва-
риантов изоморфизма) вычислительная сложность алгоритма оценивается как
2( ),nO m n где m – размерность квадратной матрицы ,A n – размерность матрицы
.B Если же алгоритм применяется для фильтрации или выборки k подобных
информационных структур, хранящихся в массиве, в худшем случае его вычис-
лительная сложность оценивается по формуле 2( ! ).nO k m n
Для ускорения работы алгоритма и повышения его эффективности
(при обработке массива информационных структур) используется распаралле-
ливание. В процессе разработки алгоритма применялась библиотека MPICH2,
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ПОИСКА И ИДЕНТИФИКАЦИИ ...
Компьютерная математика. 2015, № 1 53
представляющая собой реализацию интерфейса MPI (www.mpich.org) для Win-
dows. В параллельной версии алгоритма попарное сравнение информационных
структур выполняется в отдельных потоках, каждый из которых выполняется на
отдельном вычислительном узле.
Если количество вычислительных узлов (p) больше или равно количеству
сравниваемых информационных структур (k), вычислительная сложность алго-
ритма оценивается по формуле 2( ).nO tm n В данном случае t – коэффициент
потерь, вызванных издержками, имеющими место при коммуникации между
параллельными процессами. Если же количество вычислительных узлов (p)
меньше количества сравниваемых информационных структур (k), вычислитель-
ная сложность алгоритма будет оцениваться по формуле ))!/(( 2nmpkO n .
Результаты тестирования алгоритма. Для тестирования алгоритма при-
менялась система, состоящая из двух компьютеров, оборудованных двухядер-
ными процессорами. На первом компьютере установлена Windows 7, на вто-
ром – Windows XP. Полученные результаты приведены в таблице.
ТАБЛИЦА. Результаты тестирования алгоритма поиска и идентификации
подобных информационных структур
Кол-во
матриц
смеж-
ности в
(k)
Размерно-
сти матриц
смежности
Время выполне-
ния последова-
тельной версии
алгоритма (сек)
Время
выполнения
параллель-
ной версии
алгоритма
(сек), 1 узел
Время
выполнения
параллель-
ной версии
алгоритма
(сек), 2 узла
Время
выполнения
параллель-
ной версии
алгоритма
(сек), 4 узла
20×20 0,18 0,20 0,17 0,13
40×40 0,46 0,53 0,37 0,29
60×60 1,22 1,30 0,93 0,72
80×80 4,24 4,41 3,36 2,97
100
100×100 10,51 11,55 8,14 5,73
20×20 2,40 2,85 1,85 1,24
40×40 6,36 6,73 4,27 3,04
60×60 17,84 19,49 13,38 9,72
80×80 57,11 61,05 49,62 37,84
1000
100×100 147,42 152,74 119,63 88,12
20×20 63,04 68,72 52,79 38,07
40×40 162,94 172,93 126,37 82,83
60×60 437,87 448,25 312,63 183,06
80×80 1183,02 1203,72 837,71 682,37
5000
100×100 2943,74 3006,23 2139,58 1193,94
На рис. 2 показаны графики, отображающие результаты тестирования алго-
ритма на массиве, включающем 5000 матриц смежности информационных
структур.
А.П. СЕРГЕЕВ
54 Компьютерная математика. 2015, № 1
РИС. 2. Графики, иллюстрирующие результаты тестирования алгоритма
На вертикальной оси отложено время выполнения теста, выраженное в се-
кундах, на горизонтальной оси размерности матриц смежности.
Применение алгоритма поиска и идентификации подобных информа-
ционных структур в компьютерной химии. В качестве информационных
структур используются графо-подобные объекты (так называемые молекуляр-
ные графы), моделирующие структурные формулы химических соединений. На
рис. 3 показана структурная формула пентана, а на рис. 4 – соответствующий
этой формуле молекулярный граф.
РИС. 3. Структурная формула молекулы
пентана
РИС. 4. Молекулярный граф,
соответствующий структурной
формуле молекулы пентана
Молекулярные графы, применяемые в компьютерной химии, представлены
матрицами смежности как показано на рис. 5.
В силу однозначности представления на основе матрицы смежности можно
восстановить структурную формулу молекулы химического соединения.
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ПОИСКА И ИДЕНТИФИКАЦИИ ...
Компьютерная математика. 2015, № 1 55
С помощью алгоритма поиска и идентификации подобных информацион-
ных структур выполняется проверка матриц смежности, представляющих моле-
кулярные графы соответствующих химических соединений. Если данные мат-
рицы равны с точностью до перестановки строк и столбцов, соответствующие
молекулярные графы изоморфны, следовательно, тестируемые химические со-
единения подобны [1].
Подобные химические соединения являются стереоизомерами, относящи-
мися к одной из следующих категорий:
оптические изомеры (рис. 6);
диастереомеры;
геометрические изомеры.
Категории соединений в перечне приведены в порядке уменьшения химиче-
ского подобия. Наименьшая степень химического подобия присуща геометриче-
ским изомерам. Эти изомеры обладают разными физическими и химическими
характеристиками. Справедливо утверждение.
Утверждение 2. Молекулярные графы, соответствующие геометрическим
изомерам, неизоморфны. Справедливость этого утверждения вытекает из опре-
делений изоморфизма и геометрических изомеров [5].
Наиболее близким «сродством» обладают оптические изомеры (энантиомеры).
Данные соединения – это зеркальное отражение друг друга, которые не могут со-
вмещаться в пространстве (свойство хиральности). Имеет место утверждение.
Утверждение 3. Молекулярные графы, соответствующие оптическим изо-
мерам, будут изоморфными. Истинность этого утверждения вытекает из опреде-
ления изоморфизма и сущности оптической изомерии.
РИС. 5. Матрица смежности, соответ-
ствующая молекуле пентана
РИС. 6. Молекула офлоксацина
представляет собой комбинацию
двух оптических изомеров
А.П. СЕРГЕЕВ
56 Компьютерная математика. 2015, № 1
Благодаря применению алгоритма поиска и идентификации подобных ин-
формационных структур в компьютерной химии можно осуществлять поиск оп-
тических изомеров химических соединений, а также конструировать химические
соединения с заранее заданными свойствами.
Заключение. Рассмотрен алгоритм поиска и идентификации подобных ин-
формационных структур. Выполнена оценка вычислительной сложности алго-
ритма, описано практическое применение алгоритма в компьютерной химии.
О.П. Сергеєв
ПАРАЛЕЛЬНИЙ АЛГОРИТМ ПОШУКУ ТА ІДЕНТИФІКАЦІЇ ПОДІБНИХ
ІНФОРМАЦІЙНИХ СТРУКТУР
Запропоновано паралельний алгоритм пошуку та ідентифікації подібних інформаційних
структур. За допомогою цього алгоритму можна фільтрувати еквівалентні інформаційні
структури та виконувати вибірку даних на базі обраного шаблону. Виконано оцінку обчис-
лювальної складності алгоритму, а також проведене тестування послідовної та паралельної
версій алгоритму. Наведене практичне застосування алгоритму у компь’ютерній хімії.
A.P. Sergeyev
PARALLEL ALGORITHM FOR SEARCH AND IDENTIFICATION OF SIMILAR INFORMA-
TION STRUCTURES
The paper gives an overview of parallel algorithm for searching and identification of similar infor-
mation structures. This algorithm can be applied to filter the equivalent information structures and
retrieving data in a predetermined pattern. The evaluation of the computational complexity is given
and results of the test series and parallel version of the algorithm are presented. The application of
the algorithm in computational chemistry is described.
1. Sergeyev A.P. Fast algorithm of identification of similar chemical compounds // In Proceedings
of conference PDCS 2013, Ukraine, Charkiv, March 13 – 14, 2013. – Р. 299 – 300.
2. Sergeyev A.P. Parallel algorithm of identification of similar chemical compounds // In Proceed-
ings of conference HPC-UA 2014, Ukraine, Kyiv, October 14, 2013. – Р. 104 – 107.
3. Сергеев А.П. Быстрый алгоритм фильтрации изоморфных XSD-схем // Материалы кон-
ференции HPC-UA 2011, Украина, Киев, 12 – 14 октября 2014. – С. 122 – 126.
4. Ulmann J.R. An algorithm for Subgraph Isomorphism // National Physical Laboratory, Ted-
dington, Middlesex, England, 1976.
5. Johnson M.A., Maggiora G.M. Concepts and Applications of Molecular Similarity // New
York: John Wiley & Sons, 1990.
Получено 02.02.2015
Об авторе:
Сергеев Александр Петрович,
научный редактор, издательство «Диалектика», Киев, Украина.
|