Proliferation of touch-based devices has made the idea of sketch-based image retrieval practical. While many methods exist for sketch-based image retrieval on small datasets, little work has been done on large (web)-scale image retrieval. In this paper, we present an efficient approach for image retrieval from millions of images based on user-drawn sketches. Unlike existing methods which are sensitive to even translation or scale variations, our method handles translation, scale, rotation (similarity) and small deformations. To make online retrieval fast, each database image is preprocessed to extract sequences of contour segments (chains) that capture sufficient shape information which are represented by succinct variable length descriptors. Chain similarities are computed by a fast Dynamic Programming-based approximate substring matching algorithm, which enables partial matching of chains. Finally, hierarchical k-medoids based indexing is used for very fast retrieval in a few seconds on databases with millions of images. Qualitative and quantitative results clearly demonstrate superiority of the approach over existing methods. © 2014 Springer International Publishing.