Быстрый поиск сходных графов по расстоянию редактирования
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных деревьями и графами. В качестве меры сходства использовано расстояние редактирования. Рассмотрено выполнение запросов точного поиска по сходству. В основном представлены алгоритмы на основе стратегии фильтрации и у...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.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 |
irk-123456789-181448 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1814482021-11-18T01:26:40Z Быстрый поиск сходных графов по расстоянию редактирования Рачковский, Д.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных деревьями и графами. В качестве меры сходства использовано расстояние редактирования. Рассмотрено выполнение запросов точного поиска по сходству. В основном представлены алгоритмы на основе стратегии фильтрации и уточнения, использующие обратное индексирование. Кроме того, рассмотрены алгоритмы точного вычисления расстояния редактирования графов и его нижних и верхних границ. Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, поданих деревами та графами. Як міру схожості використано відстань редагування. Розглянуто виконання запитів точного пошуку за схожістю. В основному описано алгоритми на основі стратегії фільтрації та уточнення, які використовують обернене індексування. Крім того, розглянуто алгоритми точного обчислення відстані редагування графів та її нижніх і верхніх меж. 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. 2019 Article Быстрый поиск сходных графов по расстоянию редактирования / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 178–194. — Бібліогр.: 70 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/181448 004.22+004.93'11 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| spellingShingle |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Рачковский, Д.А. Быстрый поиск сходных графов по расстоянию редактирования Кибернетика и системный анализ |
| description |
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных деревьями и графами. В качестве меры сходства использовано расстояние редактирования. Рассмотрено выполнение запросов точного поиска по сходству. В основном представлены алгоритмы на основе стратегии фильтрации и уточнения, использующие обратное индексирование. Кроме того, рассмотрены алгоритмы точного вычисления расстояния редактирования графов и его нижних и верхних границ. |
| format |
Article |
| author |
Рачковский, Д.А. |
| author_facet |
Рачковский, Д.А. |
| author_sort |
Рачковский, Д.А. |
| title |
Быстрый поиск сходных графов по расстоянию редактирования |
| title_short |
Быстрый поиск сходных графов по расстоянию редактирования |
| title_full |
Быстрый поиск сходных графов по расстоянию редактирования |
| title_fullStr |
Быстрый поиск сходных графов по расстоянию редактирования |
| title_full_unstemmed |
Быстрый поиск сходных графов по расстоянию редактирования |
| title_sort |
быстрый поиск сходных графов по расстоянию редактирования |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2019 |
| topic_facet |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/181448 |
| citation_txt |
Быстрый поиск сходных графов по расстоянию редактирования / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 178–194. — Бібліогр.: 70 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT račkovskijda bystryjpoiskshodnyhgrafovporasstoâniûredaktirovaniâ |
| first_indexed |
2023-10-18T22:52:25Z |
| last_indexed |
2023-10-18T22:52:25Z |
| _version_ |
1796156656592093184 |