web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0000719131
Cybernetics and Systems Analysis   А - 2019 /  Issue (2017, Т. 53, № 4)
Рачковский Д. А.
Основанные на расстояниях индексные структуры для быстрого поиска по сходству Рассмотрен класс таких индексных структур для быстрого поиска по сходству, при конструировании и применении которых используется только информация о значениях или ранге некоторых расстояний/сходств между объектами. Обсужден поиск как по метрическим расстояниям (для последних выполняется неравенство треугольника и другие метрические аксиомы), так и по неметрическим. Приведены структуры, которые возвращают объекты базы, являющиеся точным ответом на поисковый запрос, а также структуры для приближенного поиска по сходству (они не гарантируют точность, но обычно возвращают близкие к точным результаты и работают быстрее структур для точного поиска). Изложены общие принципы конструирования и применения некоторых индексных структур, а также рассмотрены идеи, лежащие в основе конкретных алгоритмов, как известных, так и предложенных в последнее время.
 https://doi.org/10.1007/s10559-017-9966-y
 Scopus
Бібліографічний опис:
Рачковский Д. А. Основанные на расстояниях индексные структуры для быстрого поиска по сходству. Кибернетика и системный анализ. 2017. Т. 53, № 4. С. 165-192. doi: https://doi.org/10.1007/s10559-017-9966-y URL: http://jnas.nbuv.gov.ua/article/UJRN-0000719131 |
 Cybernetics and Systems Analysis / Issue (2017, 53 (4))
Rachkovskij D.A.
Distance-based index structures for fast similarity search This review considers the class of index structures for fast similarity search. In constructing and applying such structures, only information on values or ranks of some distances/similarities between objects is used. The search by metric distances (satisfying the triangle inequality and other metric axioms) and by nonmetric distances is discussed. Structures that return objects of a base that represent the exact answer to a search query and also structures for approximate similarity search are presented (the latter structures do not guarantee precision, but usually return results close to exact and operate faster than structures for exact search). General principles of construction and application of some index structures are stated, and also ideas underlying concrete algorithms (both well-known and proposed lately) are considered. © 2017, Springer Science+Business Media, LLC. Keywords: branch and bound method, distance-based indexing, index structure, metric distance, metric tree, nearest neighbor search, neighborhood graph, nonmetric distance, similarity search, Nearest neighbor search, Query processing, Trees (mathematics), Distance-based indexing, Index structure, Metric distances, Metric trees, Neighborhood graphs, Non-Metric, Similarity search, Branch and bound method
Cite:
Rachkovskij D.A.
(2017). Distance-based index structures for fast similarity search. Cybernetics and Systems Analysis, 53 (4), 165-192. doi: https://doi.org/10.1007/s10559-017-9966-y http://jnas.nbuv.gov.ua/article/UJRN-0000719131 [In Russian]. |
PDF