Иерархический навигационный маленький мир

Алгоритм иерархического навигационного маленького мира ( HNSW ) представляет собой графов на основе метод приближенного поиска ближайших соседей , используемый во многих векторных базах данных . ^[1]^[2] Поиск ближайшего соседа без индекса включает вычисление расстояния от запроса до каждой точки в базе данных, что для больших наборов данных является непомерно вычислительным. Для многомерных данных методы точного векторного поиска на основе деревьев, такие как дерево kd и R-дерево, не работают достаточно хорошо из-за проклятия размерности . Чтобы исправить это, приблизительные были предложены поиски k-ближайших соседей, такие как локально-зависимое хеширование (LSH) и квантование произведения (PQ), в которых производительность жертвуется ради точности. ^[2] Граф HNSW предлагает приблизительный поиск k-ближайшего соседа, который логарифмически масштабируется даже в многомерных данных.

Это расширение более ранней работы над навигационными графами маленького мира, представленной на конференции по поиску сходства и приложениям (SISAP) в 2012 году, с дополнительной иерархической навигацией для более быстрого поиска точек входа в основной граф. ^[3] Библиотеки на основе HNSW являются одними из лучших в приблизительном тесте ближайших соседей. ^[4]^[5]^[6]

Использование в векторных базах данных

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

Apache Lucene Векторный поиск
Цветность
ФАИСС
Кдрант
Веспа
Веека Гамма
Плетение
pgvector
МарияДБ ^[7]

Некоторые из них используют библиотеку hnswlib. ^[8] предоставлены первоначальными авторами.

Ссылки

^ Малков Ю А.; Яшунин, Д.А. (2016). «Эффективный и надежный приблизительный поиск ближайшего соседа с использованием иерархических навигационных графиков маленького мира». arXiv : 1603.09320 [ cs.DS ].
^ Jump up to: ^а ^б Малков Юрий А; Яшунин, Дмитрий А (1 апреля 2020 г.). «Эффективный и надежный приблизительный поиск ближайшего соседа с использованием иерархических навигационных графиков маленького мира». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 42 (4): 824–836. arXiv : 1603.09320 . дои : 10.1109/TPAMI.2018.2889473 . ПМИД 30602420 .
^ Малков Юрий; Пономаренко Александр; Логвинов Андрей; Крылов, Владимир (2012). «Масштабируемый распределенный алгоритм для задачи приближенного поиска ближайших соседей в многомерных общих метрических пространствах» . В Наварро — Гонсало; Пестов, Владимир (ред.). Поиск по сходству и его применение . Конспекты лекций по информатике. Том. 7404. Берлин, Гейдельберг: Springer. стр. 132–147. дои : 10.1007/978-3-642-32153-5_10 . ISBN 978-3-642-32153-5 .
^ Аумюллер, Мартин; Бернхардссон, Эрик; Верный, Александр (2017). «ANN-Benchmarks: инструмент сравнительного анализа приближенных алгоритмов ближайшего соседа» . В Биксе, Кристиан; Борутта, Феликс; Крегер, Пер; Зайдль, Томас (ред.). Поиск по сходству и его применение . Конспекты лекций по информатике. Том. 10609. Чам: Springer International Publishing. стр. 34–49. arXiv : 1807.05614 . дои : 10.1007/978-3-319-68474-1_3 . ISBN 978-3-319-68474-1 .
^ Аумюллер, Мартин; Бернхардссон, Эрик; Верный, Александр (2020). «ANN-Benchmarks: инструмент сравнительного анализа приблизительных алгоритмов ближайшего соседа» . Информационные системы . 87 : 101374. arXiv : 1807.05614 . дои : 10.1016/j.is.2019.02.006 .
^ «ИНН-Бенчмарки» . ann-benchmarks.com . Проверено 19 марта 2024 г.
^ «МарияДБ Вектор» . MariaDB.org . Проверено 30 июля 2024 г.
^ nmslib/hnswlib , nmslib, 18 марта 2024 г. , получено 19 марта 2024 г.

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

Эта статья о компьютерах незавершена . Вы можете помочь Википедии, расширив ее .

[1] Малков Ю А.; Яшунин, Д.А. (2016). «Эффективный и надежный приблизительный поиск ближайшего соседа с использованием иерархических навигационных графиков маленького мира». arXiv : 1603.09320 [ cs.DS ].

[hnsw-2] Jump up to: ^а ^б Малков Юрий А; Яшунин, Дмитрий А (1 апреля 2020 г.). «Эффективный и надежный приблизительный поиск ближайшего соседа с использованием иерархических навигационных графиков маленького мира». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 42 (4): 824–836. arXiv : 1603.09320 . дои : 10.1109/TPAMI.2018.2889473 . ПМИД 30602420 .

[3] Малков Юрий; Пономаренко Александр; Логвинов Андрей; Крылов, Владимир (2012). «Масштабируемый распределенный алгоритм для задачи приближенного поиска ближайших соседей в многомерных общих метрических пространствах» . В Наварро — Гонсало; Пестов, Владимир (ред.). Поиск по сходству и его применение . Конспекты лекций по информатике. Том. 7404. Берлин, Гейдельберг: Springer. стр. 132–147. дои : 10.1007/978-3-642-32153-5_10 . ISBN 978-3-642-32153-5 .

[4] Аумюллер, Мартин; Бернхардссон, Эрик; Верный, Александр (2017). «ANN-Benchmarks: инструмент сравнительного анализа приближенных алгоритмов ближайшего соседа» . В Биксе, Кристиан; Борутта, Феликс; Крегер, Пер; Зайдль, Томас (ред.). Поиск по сходству и его применение . Конспекты лекций по информатике. Том. 10609. Чам: Springer International Publishing. стр. 34–49. arXiv : 1807.05614 . дои : 10.1007/978-3-319-68474-1_3 . ISBN 978-3-319-68474-1 .

[5] Аумюллер, Мартин; Бернхардссон, Эрик; Верный, Александр (2020). «ANN-Benchmarks: инструмент сравнительного анализа приблизительных алгоритмов ближайшего соседа» . Информационные системы . 87 : 101374. arXiv : 1807.05614 . дои : 10.1016/j.is.2019.02.006 .

[6] «ИНН-Бенчмарки» . ann-benchmarks.com . Проверено 19 марта 2024 г.

[7] «МарияДБ Вектор» . MariaDB.org . Проверено 30 июля 2024 г.

[8] nmslib/hnswlib , nmslib, 18 марта 2024 г. , получено 19 марта 2024 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]