Binary search trees for vector quantisation
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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 is presented.
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 is k + 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.