Vector excitation coding (VXC) is a speech digitisation technique growing in popularity. Problems associated with VXC systems are high computational complexity and poor reconstruction of plosives. The Pairwise Nearest Neighbour (PNN) clustering algorithm is proposed as an efficient method of codebook design. It is demonstrated to preserve plosives better than the Linde-Buzo-Gary (LBG) algorithm [34] and maintain similar quality to LBG for other speech Classification of the residual is then studied. This reduces codebook search complexity and enables a shortcut in computation of the PNN algorithm to be exploited.