Метод швидкого пошуку найближчого сусіда з обчисленням відстані за зваженою евклідовою метрикою

Abstract

Поставлено і розв’язано задачу підвищення продуктивності комп’ютерних систем для обробки мультимедійної, зокрема, голосової інформації за рахунок зменшення часу пошуку найближчого вектора у словнику великого розміру. Розроблено підхід на основі kd-дерева, що поєднує переваги методів швидкого пошуку найближчого сусіда із застосуванням зваженої евклідової метрики. Досягнуте зниження обчислювальної складності робить можливою реалізацію запропонованого методу на процесорах з обмеженою продуктивністю.

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

The problem of improving the performance of computer systems for multimedia, including voice information, by reducing the vector quantization time in codebooks. The approach based on the kd-tree is developed that combines the advantages of fast vector search and using the weighted Euclidean metric. Achieved reduction in computational complexity enables the implementation of the proposed method on processors with limited capacity.