Content-based image indexing is emerging as an important research area with application to digital libraries and multimedia databases. A majority of indexing techniques are based on pixel domain features such as histogram, color, texture, and shape. However, with recent advances in image compression, compressed domain indexing techniques are gaining popularity due to their low complexity. Recently, a wavelet histogram technique which exploits the directional properties of wavelet transform has been proposed in the literature. Although, this technique provides a good retrieval performance for texture images, its complexity is very high. In this paper, we propose three techniques to reduce the complexity of the wavelet histogram method. These techniques together provide a superior performance at a substantially reduced complexity and, hence, can be considered as a potential candidate for developing a joint wavelet-based image storage and retrieval system.