Поиск по сходству

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

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

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

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

Поиск по метрике [ править ]

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

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

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

Типы [ править ]

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

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

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

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

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

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

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

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

ANN-Benchmarks , для алгоритмов приблизительного поиска ближайших соседей; от Spotify

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

^ Гионис, Аристид, Петр Индик и Раджив Мотвани. «Поиск сходства в больших измерениях посредством хеширования». ВЛДБ. Том. 99. № 6. 1999.
^ Раджараман, А.; Ульман, Дж. (2010). «Анализ больших наборов данных, глава 3» .

[1] Гионис, Аристид, Петр Индик и Раджив Мотвани. «Поиск сходства в больших измерениях посредством хеширования». ВЛДБ. Том. 99. № 6. 1999.

[2] Раджараман, А.; Ульман, Дж. (2010). «Анализ больших наборов данных, глава 3» .

[1]

[2]