We propose a novel approach that combines the space covering property of high rate lattice VQ with the pattern matching ability of clustering VQ. The proposed scheme encompasses a broad range of online algorithms that use suitable VQ encodings and fixed-size, adaptive codebooks. The generic baseline algorithm for the scheme has the following desirable characterstics. The distortion per individual vector is guaranteed to be less than a user specified threshold. Secondly, the algorithm is amenable to fast realtime implementation and requires minimal statistical assumption for analysis. Finally, with careful analysis, the coding rate can be bounded with respect to some theoretical benchmark.