Поиск сходства

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

Поиск ближайшего соседа и запросы диапазона являются важными подклассами поиска по сходству, и существует ряд решений. В исследованиях поиска по сходству преобладают проблемы, присущие поиску сложных объектов. Такие объекты приводят к тому, что большинство известных методов теряют контроль над большими коллекциями из-за проявления так называемого проклятия размерности , и остается еще много нерешенных проблем. К сожалению, во многих случаях, когда необходим поиск сходства, объекты по своей сути сложны.

Самый общий подход к поиску сходства основан на математическом понятии метрического пространства , которое позволяет создавать эффективные структуры индекса для достижения масштабируемости в области поиска.

Поиск сходства развивался независимо в различных научных и компьютерных контекстах в соответствии с различными потребностями. В 2008 году несколько ведущих исследователей в этой области твердо считали, что этот предмет должен быть самостоятельной темой исследования, чтобы позволить сосредоточиться на общих вопросах, применимых во многих различных областях его использования. Это привело к формированию фонда SISAP , основным направлением деятельности которого является серия ежегодных международных конференций по общей теме.

Метрический поиск [ править ]

Метрический поиск - это поиск подобия, который происходит в метрических пространствах . В то время как полуметрические свойства более или менее необходимы для того, чтобы любой вид поиска был значимым, дополнительное свойство неравенства треугольника полезно для инженерных, а не концептуальных целей.

Простое следствие неравенства треугольника состоит в том, что если любые два объекта в пространстве находятся далеко друг от друга, то ни один третий объект не может быть близок к обоим. Это наблюдение позволяет строить структуры данных на основе расстояний, измеренных в рамках сбора данных, что позволяет исключать подмножества данных при выполнении запроса. В качестве простого примера, эталонный объект может быть выбран из набора данных, а оставшаяся часть набора разделена на две части в зависимости от расстояния до этого объекта: те, которые находятся рядом с эталонным объектом в наборе A , и те, которые находятся далеко от объекта в множество Б . Если при последующем запросе набора расстояние от запроса до ссылочного объекта велико, то ни один из объектов в наборе Aможет быть очень близок к запросу; если он очень маленький, то ни один объект в наборе B не может быть близок к запросу.

После количественной оценки и изучения таких ситуаций можно разработать множество различных структур индексации показателей, по-разному подходящих для разных типов коллекций. Таким образом, область исследования метрического поиска можно охарактеризовать как изучение алгоритмов предварительной обработки больших и относительно статических наборов данных, которые, используя свойства метрических пространств, позволяют выполнять эффективный поиск сходства.

Другие типы поиска сходства [ править ]

Хеширование с учетом местоположения [ править ]

Популярным подходом к поиску сходства является хеширование с учетом местоположения (LSH). ^[1] хеширует входные элементы так, чтобы похожие элементы отображались в одни и те же «сегменты» в памяти с высокой вероятностью (количество сегментов намного меньше, чем набор возможных входных элементов). Он часто применяется при поиске ближайшего соседа к крупномасштабным данным большой размерности, например, к базам данных изображений, коллекциям документов, базам данных временных рядов и базам данных генома. ^[2]

Контрольные показатели [ править ]

http://ann-benchmarks.com/ - ANN-Benchmarks - это тестовая среда для приблизительного поиска алгоритмов ближайшего соседа, она была создана группой рекомендаций Spotify.

См. Также [ править ]

Фонд SISAP и серия конференций: www.sisap.org

• Изучение подобия
• Скрытый семантический анализ

Библиография [ править ]

• Пей Ли, Лакс В.С. Лакшманан, Джеффри Сюй Ю: Поиск структурного подобия на вершине. ICDE 2012: 774-785
• Зезула П., Амато Г., Дохнал В., Батько М. Поиск подобия - подход в метрическом пространстве. Springer, 2006. ISBN  0-387-29146-6.
• Самет, Х .. Основы многомерных и метрических структур данных. Морган Кауфманн, 2006. ISBN 0-12-369446-9 
• Э. Чавес, Дж. Наварро, Р. А. Баеза-Йейтс, Дж. Л. Маррокин, Поиск в метрических пространствах , ACM Computing Surveys, 2001
• М.Л. Хетланд, Основные принципы индексирования показателей , Swarm Intelligence для многоцелевых задач интеллектуального анализа данных, Исследования в области вычислительного интеллекта, том 242, 2009 г., стр. 199–232

Ресурсы [ править ]

• Проект Multi-Feature Indexing Network (MUFIN)
• MI-файл (метрический инвертированный файл)
• Контентная коллекция тестов для поиска фотоизображений (CoPhIR)

Ссылки [ править ]