A vector quantization fast search algorithm using hyperplane based k-dimensional multi-node search tree is presented. Misclassification problem associated with hyperplane decision is eliminated by a multi-level back-tracing algorithm. The vector quantization complexity is further lowered by a novel relative distance quantization rule. Triangular inequality is applied to lower bound the search distance, thus eliminated all the sub-tree in the k-dimensional search tree during back-tracing. Vector quantization image coding results are presented which showed the proposed algorithm outperform other algorithms in literature both in PSNR and computation time.