Binary search trees for vector quantisation

Abstract

This paper presents a data structure based on the k-d binary tree which substantially reduces the search complexity of a full search vector quantiser with negligible degradation in signal-to-noise ratio. The search complexity isk + O(\logN)rather than N for a codebook of dimension k and size N. Special features of the structure are (1) the use of a rotational transform prior to encoding and (2) the computational efficiency of the design algorithm due to the simple structure of the k-d tree.