Fast retrieval of images from large databases especially from large medical image databases is of great interest to researchers. We have developed shape-based image retrieval system for spine X-ray images that applies Dynamic Programming (DP) in Partial Shape Matching (PSM) techniques to vertebral boundary data. As we enable Internet access to this system with an aim to enable CBIR access to the entire NHANES II spine X-ray image collection, retrieval efficiency has become critical. In this paper, we present enhancements to our existing sequential retrieval model to provide faster partialshape- based vertebrae retrieval. Based on the characteristics of vertebral osteophyte pathology, anterior superior and anterior inferior parts are the areas with the most interest to the users and are indexed for each shape. Pair-wise distances between indexed parts are pre-calculated and used by agglomerative clustering algorithm to index the whole database. To increase the retrieval speed, PSM with DP is therefore conducted only on a small selected set of shapes by the pre-indexing retrieval.