Индексные структуры для быстрого поиска по сходству вещественных векторов. II
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены структуры как для точного, так и для более быстрого, но приближенного поиска. Представлены главным образом индексные структуры на основе разбиения на области (в том числе иерарх...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2018 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/144862 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Индексные структуры для быстрого поиска по сходству вещественных векторов. II / Д.А. Рачковский // Кибернетика и системный анализ. — 2018. — Т. 54, № 2. — С. 162–181. — Бібліогр.: 118 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862732991860572160 |
|---|---|
| author | Рачковский, Д.А. |
| author_facet | Рачковский, Д.А. |
| citation_txt | Индексные структуры для быстрого поиска по сходству вещественных векторов. II / Д.А. Рачковский // Кибернетика и системный анализ. — 2018. — Т. 54, № 2. — С. 162–181. — Бібліогр.: 118 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены структуры как для точного, так и для более быстрого, но приближенного поиска. Представлены главным образом индексные структуры на основе разбиения на области (в том числе иерархические) и графов соседства. Обсуждено также ускорение поиска по сходству с использованием преобразования исходных данных. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Проведено сравнение подходов к ускорению поиска по сходству в индексных структурах рассмотренных типов, а также на основе сохраняющего сходство хэширования.
Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені дійсними векторами. Розглянуто структури як для точного, так і для наближеного пошуку. Проаналізовано головним чином індексні структури на основі розбиття на області (у тому числі ієрархічні) та графів сусідства. Обговорено також прискорення пошуку за схожістю з використанням перетворення вхідних даних. Викладено ідеї конкретних алгоритмів (відомих та нещодавно запропонованих). Наведено порівняння підходів до прискорення пошуку за схожістю в індексних структурах розглянутих типів, а також на основі хешування, що зберігає схожість.
In this survey paper, we consider index structures for fast similarity search of objects represented by real-valued vectors. Structures for both exact and faster, but approximate, similarity search are considered. We present index structures mainly on the basis of partitioning into regions (including hierarchical ones) and neighborhood graphs. The acceleration of the similarity search using the transformation of the original data is also discussed. The ideas of specific algorithms, including the recently proposed ones, are outlined. The approaches to the speed-up of similarity search in the index structures of the considered types and those based on similarity-preserving hashing are discussed and compared.
|
| first_indexed | 2025-12-07T19:35:19Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-144862 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T19:35:19Z |
| publishDate | 2018 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Рачковский, Д.А. 2019-01-05T19:46:43Z 2019-01-05T19:46:43Z 2018 Индексные структуры для быстрого поиска по сходству вещественных векторов. II / Д.А. Рачковский // Кибернетика и системный анализ. — 2018. — Т. 54, № 2. — С. 162–181. — Бібліогр.: 118 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/144862 004.22+004.93'11 Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены структуры как для точного, так и для более быстрого, но приближенного поиска. Представлены главным образом индексные структуры на основе разбиения на области (в том числе иерархические) и графов соседства. Обсуждено также ускорение поиска по сходству с использованием преобразования исходных данных. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Проведено сравнение подходов к ускорению поиска по сходству в индексных структурах рассмотренных типов, а также на основе сохраняющего сходство хэширования. Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені дійсними векторами. Розглянуто структури як для точного, так і для наближеного пошуку. Проаналізовано головним чином індексні структури на основі розбиття на області (у тому числі ієрархічні) та графів сусідства. Обговорено також прискорення пошуку за схожістю з використанням перетворення вхідних даних. Викладено ідеї конкретних алгоритмів (відомих та нещодавно запропонованих). Наведено порівняння підходів до прискорення пошуку за схожістю в індексних структурах розглянутих типів, а також на основі хешування, що зберігає схожість. In this survey paper, we consider index structures for fast similarity search of objects represented by real-valued vectors. Structures for both exact and faster, but approximate, similarity search are considered. We present index structures mainly on the basis of partitioning into regions (including hierarchical ones) and neighborhood graphs. The acceleration of the similarity search using the transformation of the original data is also discussed. The ideas of specific algorithms, including the recently proposed ones, are outlined. The approaches to the speed-up of similarity search in the index structures of the considered types and those based on similarity-preserving hashing are discussed and compared. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Индексные структуры для быстрого поиска по сходству вещественных векторов. II Індексні структури для швидкого пошуку за схожістю дійсних векторів. II Index structures for fast similarity search of real-valued vectors. II Article published earlier |
| spellingShingle | Индексные структуры для быстрого поиска по сходству вещественных векторов. II Рачковский, Д.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| title | Индексные структуры для быстрого поиска по сходству вещественных векторов. II |
| title_alt | Індексні структури для швидкого пошуку за схожістю дійсних векторів. II Index structures for fast similarity search of real-valued vectors. II |
| title_full | Индексные структуры для быстрого поиска по сходству вещественных векторов. II |
| title_fullStr | Индексные структуры для быстрого поиска по сходству вещественных векторов. II |
| title_full_unstemmed | Индексные структуры для быстрого поиска по сходству вещественных векторов. II |
| title_short | Индексные структуры для быстрого поиска по сходству вещественных векторов. II |
| title_sort | индексные структуры для быстрого поиска по сходству вещественных векторов. ii |
| topic | Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| topic_facet | Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/144862 |
| work_keys_str_mv | AT račkovskiida indeksnyestrukturydlâbystrogopoiskaposhodstvuveŝestvennyhvektorovii AT račkovskiida índeksnístrukturidlâšvidkogopošukuzashožístûdíisnihvektorívii AT račkovskiida indexstructuresforfastsimilaritysearchofrealvaluedvectorsii |