Основанные на расстояниях индексные структуры для быстрого поиска по сходству
Рассмотрен класс таких индексных структур для быстрого поиска по сходству, при конструировании и применении которых используется только информация о значениях или ранге некоторых расстояний/сходств между объектами. Обсужден поиск как по метрическим расстояниям (для последних выполняется неравенство...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/144783 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Основанные на расстояниях индексные структуры для быстрого поиска по сходству / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 165–192. — Бібліогр.: 148 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-144783 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1447832019-01-04T01:23:18Z Основанные на расстояниях индексные структуры для быстрого поиска по сходству Рачковский, Д.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Рассмотрен класс таких индексных структур для быстрого поиска по сходству, при конструировании и применении которых используется только информация о значениях или ранге некоторых расстояний/сходств между объектами. Обсужден поиск как по метрическим расстояниям (для последних выполняется неравенство треугольника и другие метрические аксиомы), так и по неметрическим. Представлены структуры, которые возвращают объекты базы, являющиеся точным ответом на поисковый запрос, а также структуры для приближенного поиска по сходству (они не гарантируют точность, но обычно возвращают близкие к точным результаты и работают быстрее структур для точного поиска). Изложены общие принципы конструирования и применения некоторых индексных структур, а также рассмотрены идеи, лежащие в основе конкретных алгоритмов, как известных, так и предложенных в последнее время. Розглянуто клас таких індексних структур для швидкого пошуку за схожістю, при конструюванні та застосуванні яких використовують тільки інформацію про значення або ранг деяких відстаней/схожостей між об’єктами. Обговорено пошук як за метричними відстанями (для яких виконується нерівність трикутника та інші метричні аксіоми), так і за неметричними. Наведено структури, які повертають об’єкти бази, що є точною відповіддю на запит, а також структури для наближеного пошуку за схожістю (вони не гарантують точності, але зазвичай повертають близькі до точних результати та працюють швидше структур для точного пошуку). Викладено загальні принципи конструювання і застосування деяких індексних структур, а також розглянуто ідеї, на яких базуються конкретні алгоритми (відомі та запропоновані останнім часом). In this survey paper we consider the class of index structures for fast similarity search that uses for index construction and application only information about the values or ranks of some distances/similarities between objects. We discuss the search by metric distances (for which the triangle inequality and other metric axioms are valid), as well as by non-metric ones. Considered index structures include those returning the objects of the base that are exact results to the similarity search query, and index structures for approximate similarity search, which do not guarantee the accuracy, but usually return close to accurate results and work faster than the structures for exact search. Some general principles for construction and usage of index structures as well as some ideas of specific algorithms, including recently proposed ones, are discussed. 2017 Article Основанные на расстояниях индексные структуры для быстрого поиска по сходству / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 165–192. — Бібліогр.: 148 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/144783 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 |
2017 |
| topic_facet |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/144783 |
| citation_txt |
Основанные на расстояниях индексные структуры для быстрого поиска по сходству / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 165–192. — Бібліогр.: 148 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT račkovskijda osnovannyenarasstoâniâhindeksnyestrukturydlâbystrogopoiskaposhodstvu |
| first_indexed |
2023-05-20T17:20:27Z |
| last_indexed |
2023-05-20T17:20:27Z |
| _version_ |
1796153074252775424 |