Быстрый поиск сходных графов по расстоянию редактирования
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных деревьями и графами. В качестве меры сходства использовано расстояние редактирования. Рассмотрено выполнение запросов точного поиска по сходству. В основном представлены алгоритмы на основе стратегии фильтрации и у...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2019 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/181448 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Быстрый поиск сходных графов по расстоянию редактирования / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 178–194. — Бібліогр.: 70 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-181448 |
|---|---|
| record_format |
dspace |
| spelling |
Рачковский, Д.А. 2021-11-17T14:36:52Z 2021-11-17T14:36:52Z 2019 Быстрый поиск сходных графов по расстоянию редактирования / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 178–194. — Бібліогр.: 70 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/181448 004.22+004.93'11 Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных деревьями и графами. В качестве меры сходства использовано расстояние редактирования. Рассмотрено выполнение запросов точного поиска по сходству. В основном представлены алгоритмы на основе стратегии фильтрации и уточнения, использующие обратное индексирование. Кроме того, рассмотрены алгоритмы точного вычисления расстояния редактирования графов и его нижних и верхних границ. Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, поданих деревами та графами. Як міру схожості використано відстань редагування. Розглянуто виконання запитів точного пошуку за схожістю. В основному описано алгоритми на основі стратегії фільтрації та уточнення, які використовують обернене індексування. Крім того, розглянуто алгоритми точного обчислення відстані редагування графів та її нижніх і верхніх меж. This survey article considers index structures for fast similarity search for objects represented by trees and graphs. The edit distance is used as a measure of similarity. The execution of exact similarity search queries is considered. Algorithms based on filter-and-refine strategy using inverted indexing are mainly presented. Algorithms for accurate calculation of the graph edit distance and its lower and upper bounds are also considered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Быстрый поиск сходных графов по расстоянию редактирования Швидкий пошук схожих графів за відстанню редагування Fast search for similar graphs by edit distance 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 |
2019 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Швидкий пошук схожих графів за відстанню редагування Fast search for similar graphs by edit distance |
| description |
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных деревьями и графами. В качестве меры сходства использовано расстояние редактирования. Рассмотрено выполнение запросов точного поиска по сходству. В основном представлены алгоритмы на основе стратегии фильтрации и уточнения, использующие обратное индексирование. Кроме того, рассмотрены алгоритмы точного вычисления расстояния редактирования графов и его нижних и верхних границ.
Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, поданих деревами та графами. Як міру схожості використано відстань редагування. Розглянуто виконання запитів точного пошуку за схожістю. В основному описано алгоритми на основі стратегії фільтрації та уточнення, які використовують обернене індексування. Крім того, розглянуто алгоритми точного обчислення відстані редагування графів та її нижніх і верхніх меж.
This survey article considers index structures for fast similarity search for objects represented by trees and graphs. The edit distance is used as a measure of similarity. The execution of exact similarity search queries is considered. Algorithms based on filter-and-refine strategy using inverted indexing are mainly presented. Algorithms for accurate calculation of the graph edit distance and its lower and upper bounds are also considered.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/181448 |
| citation_txt |
Быстрый поиск сходных графов по расстоянию редактирования / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 178–194. — Бібліогр.: 70 назв. — рос. |
| work_keys_str_mv |
AT račkovskiida bystryipoiskshodnyhgrafovporasstoâniûredaktirovaniâ AT račkovskiida švidkiipošukshožihgrafívzavídstannûredaguvannâ AT račkovskiida fastsearchforsimilargraphsbyeditdistance |
| first_indexed |
2025-12-07T15:27:26Z |
| last_indexed |
2025-12-07T15:27:26Z |
| _version_ |
1850863776099729408 |