Binary search trees for vector quantisation
- 24 March 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 12, 2205-2208
- https://doi.org/10.1109/icassp.1987.1169380
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.Keywords
This publication has 3 references indexed in Scilit:
- On the structure of vector quantizersIEEE Transactions on Information Theory, 1982
- An Algorithm for Vector Quantizer DesignIEEE Transactions on Communications, 1980
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975