Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search

A. Ponomarenko; N. Avrelin; Naidan B.; Boytsov L.

?

Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search

P. 125–130.

Пономаренко А. А., Аврелин Н. С., Naidan B., Boytsov L.

Similarity searching has a vast range of applications in various fields of computer science. Many methods have been proposed for exact search, but they all suffer from the curse of dimensionality and are, thus, not applicable to high dimensional spaces. Approximate search methods are considerably more efficient in high dimensional spaces. Unfortunately, there are few theoretical results regarding the complexity of these methods and there are no comprehensive empirical evaluations, especially for non-metric spaces. To fill this gap, we present an empirical analysis of data structures for approximate nearest neighbor search in high dimensional spaces. We provide a comparison with recently published algorithms on several data sets. Our results show that small world approaches provide some of the best tradeoffs between efficiency and effectiveness in both metric and non-metric spaces.

Язык: английский

Полный текст

Текст на другом сайте

Ключевые слова: metric space nearest neighbor search non-metric search approximate search small world graphs

В книге

DATA ANALYTICS 2014, The Third International Conference on Data Analytics

[б.и.], 2014.

MDProcessing.jl: Julia Programming Language Application for Molecular Dynamics Trajectory Processing

Писарев В. В., Panov M., , in: Supercomputing: 9th Russian Supercomputing Days, RuSCDays 2023, Moscow, Russia, September 25–26, 2023, Revised Selected Papers, Part II* 2.: Springer, 2023. P. 209–222.

Добавлено: 11 ноября 2025 г.

The approximate variation to pointwise selection principles

Vyacheslav V. Chistyakov, / Series arXiv [math.FA] "Functional Analysis". 2019. No. arXiv: 1910.08490.

Добавлено: 21 октября 2019 г.

Lines in hypergraphs

Боду Л., Bondy A., Chen X. и др., Combinatorica 2013 Vol. 33 No. 6 P. 633–654

Добавлено: 11 апреля 2019 г.

Совместный модуль вариации функций и условно регулярный принцип выбора

С.А.Чистякова, В.В.Чистяков, В кн.: Труды Математического центра имени Н.И.ЛобачевскогоТ. 54: Теория функций, ее приложения и смежные вопросы.: Каз.: Издательство Казанского математического общества и Академии наук РТ, 2017. С. 399–402.

Для отрезка $I=[a,b]$ и метрического пространства $(M,d)$ на множестве $M^I$ всех функций, действующих из $I$ в $M$, определяется неубывающая последовательность псевдометрик $\{\nu_n\}$, называемая {\it совместным модулем вариации}. Показано, что если две последовательности функций $\{f_j\}$ и $\{g_j\}$ из $M^I$ такие, что $\{f_j\}$ поточечно относительно компактна на $I$, $\{g_j\}$ поточечно сходящаяся на $I$ и $\limsup_{j\to\infty}\nu_n(f_j,g_j)=o(n)$ при $n\to\infty$, то $\{f_j\}$ содержит поточечно сходящуюся на $I$ ...

Добавлено: 29 августа 2017 г.

The joint modulus of variation of metric space valued functions and pointwise selection principles

Vyacheslav V. Chistyakov, Svetlana A. Chistyakova, Studia Mathematica 2017 Vol. 238 No. 1 P. 37–57

Добавлено: 11 мая 2017 г.

Pointwise selection theorems for metric space valued bivariate functions

Vyacheslav V. Chistyakov, Svetlana A. Chistyakova, Journal of Mathematical Analysis and Applications 2017 Vol. 452 No. 2 P. 970–989

Добавлено: 13 апреля 2017 г.

Theatre Plays as ‘Small Worlds’? Network Data on the History and Typology of German Drama, 1730–1930

Фишер Ф., Göbel M., Kampkaspar D. и др., , in: Digital Humanities 2016. Conference Abstracts (Jagiellonian University & Pedagogical University, Kraków, 11–16 July 2016).: Kraków: [б.и.], 2016. P. 255–258.

Decades ago, alongside more traditional structuralist paradigms that were largely based on linguistic theorems (Lotman 1972, Titzmann 1977), literary studies began to undertake structural analyses based on empirical sociology, in particular the social network analysis. Structure was no longer solely defined by semantic relations (such as opposition or equivalence), but by social interactions, too (Marcus ...

Добавлено: 9 ноября 2016 г.

СРАВНИТЕЛЬНЫЙ АНАЛИЗ СТРУКТУР ДАННЫХ ДЛЯ ПРИБЛИЖЕННОГО ПОИСКА БЛИЖАЙШЕГО СОСЕДА

Пономаренко А. А., Аврелин Н. С., Найдан Б. С. и др., Алгоритмы, методы и системы обработки данных 2015 Т. 4 № 33 С. 91–106

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

Добавлено: 27 сентября 2016 г.

Growing Homophilic Networks Are Natural Navigable Small Worlds

Мальков Ю. А., Пономаренко А. А., Plos One 2016 Vol. 11 No. 6 P. 1–14

Добавлено: 9 сентября 2016 г.

The joint modulus of variation of metric space valued functions and pointwise selection principles

Vyacheslav V. Chistyakov, Svetlana A. Chistyakova, / Series math "arxiv.org". 2016. No. 1601.07298.

Given a subset T of real numbers and a metric space M, we introduce a nondecreasing sequence {v_n} of pseudometrics on the set M^T of all functions from T into M, called the joint modulus of variation. We prove that if two sequences of functions {f_j} and {g_j} from M^T are such that {f_j} is ...

Добавлено: 12 февраля 2016 г.

Query-Based Improvement Procedure and Self-Adaptive Graph Construction Algorithm for Approximate Nearest Neighbor Search

Пономаренко А. А., Lecture Notes in Computer Science 2015 P. 314–319

Добавлено: 9 октября 2015 г.

The inverted multi-index

Бабенко А. В., Lempitsky V., IEEE Transactions on Pattern Analysis and Machine Intelligence 2015 Vol. 37 No. 6 P. 1247–1260

A new data structure for efficient similarity search in very large datasets of high-dimensional vectors is introduced. This structure called the inverted multi-index generalizes the inverted index idea by replacing the standard quantization within inverted indices with product quantization. For very similar retrieval complexity and pre-processing time, inverted multi-indices achieve a much denser subdivision of ...

Добавлено: 3 сентября 2015 г.

The Inverted Multi-Index

Babenko A., IEEE Transactions on Pattern Analysis and Machine Intelligence 2014 Vol. PP No. 99 P. 1

Добавлено: 19 декабря 2014 г.

Approximate nearest neighbor algorithm based on navigable small world graphs

Malkov Y., Ponomarenko Alexander, Krylov V. и др., Information Systems 2014 Vol. 45 No. DOI 10.1016/j.is.2013.10.006 P. 61–68

Добавлено: 24 января 2014 г.

Scalable Distributed Algorithm for Approximate Nearest Neighbor Search Problem in High Dimensional General Metric Spaces

Yury M., Пономаренко А. А., Vladimir K. и др., Lecture Notes in Computer Science 2012 No. 7404 P. 132–147

Добавлено: 1 октября 2013 г.