Основанные на расстояниях индексные структуры для быстрого поиска по сходству

• Дата: 2017
• Автор: Рачковский, Д.А.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2017
• Назва видання: Кибернетика и системный анализ
• Теми: Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/144783
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Основанные на расстояниях индексные структуры для быстрого поиска по сходству / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 165–192. — Бібліогр.: 148 назв. — рос.

Рассмотрен класс таких индексных структур для быстрого поиска по сходству, при конструировании и применении которых используется только информация о значениях или ранге некоторых расстояний/сходств между объектами. Обсужден поиск как по метрическим расстояниям (для последних выполняется неравенство треугольника и другие метрические аксиомы), так и по неметрическим. Представлены структуры, которые возвращают объекты базы, являющиеся точным ответом на поисковый запрос, а также структуры для приближенного поиска по сходству (они не гарантируют точность, но обычно возвращают близкие к точным результаты и работают быстрее структур для точного поиска). Изложены общие принципы конструирования и применения некоторых индексных структур, а также рассмотрены идеи, лежащие в основе конкретных алгоритмов, как известных, так и предложенных в последнее время.