Bag-of-visual-words or bag-of-visterms (bov) is a common technique used to index Multimedia information with the purposes of retrieval and classification. In this work we address the problem of constructing efficient bov representations of complex shapes as are the Maya syllabic hieroglyphs. Based on retrieval experiments, we assess and evaluate the performance of several variants of the recent sparse coding method KSVD, and compare it with the traditional k-means clustering algorithm. We investigate the effects of a thresholding procedure used to facilitate the sparse decomposition of signals that are potentially sparse, and we also assess the performance of different pooling techniques to construct bov representations. Although the bov's computed via Sparse Coding do not outperform the retrieval precision of those computed by k-means, they achieve competitive results after an adequate enforcement of the sparsity, which leads to more discriminative bag representations with respect to using the original non-sparse descriptors. Also, we propose a simplified formulation of the HOOSC descriptor that improves the retrieval performance.