Быстрый поиск сходных графов по расстоянию редактирования
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных деревьями и графами. В качестве меры сходства использовано расстояние редактирования. Рассмотрено выполнение запросов точного поиска по сходству. В основном представлены алгоритмы на основе стратегии фильтрации и у...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2019 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/181448 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Быстрый поиск сходных графов по расстоянию редактирования / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 178–194. — Бібліогр.: 70 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862669125565808640 |
|---|---|
| author | Рачковский, Д.А. |
| author_facet | Рачковский, Д.А. |
| citation_txt | Быстрый поиск сходных графов по расстоянию редактирования / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 178–194. — Бібліогр.: 70 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| 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.
|
| first_indexed | 2025-12-07T15:27:26Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-181448 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T15:27:26Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
| spellingShingle | Быстрый поиск сходных графов по расстоянию редактирования Рачковский, Д.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| title | Быстрый поиск сходных графов по расстоянию редактирования |
| title_alt | Швидкий пошук схожих графів за відстанню редагування Fast search for similar graphs by edit distance |
| title_full | Быстрый поиск сходных графов по расстоянию редактирования |
| title_fullStr | Быстрый поиск сходных графов по расстоянию редактирования |
| title_full_unstemmed | Быстрый поиск сходных графов по расстоянию редактирования |
| title_short | Быстрый поиск сходных графов по расстоянию редактирования |
| title_sort | быстрый поиск сходных графов по расстоянию редактирования |
| topic | Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| topic_facet | Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/181448 |
| work_keys_str_mv | AT račkovskiida bystryipoiskshodnyhgrafovporasstoâniûredaktirovaniâ AT račkovskiida švidkiipošukshožihgrafívzavídstannûredaguvannâ AT račkovskiida fastsearchforsimilargraphsbyeditdistance |