This paper examines issues arising in applying a previously developed edit-distance shock graph matching technique to indexing into large shape databases. This approach compares the shock graph topology and attributes to produce a similarity metric, and results in 100% recognition rate in querying a database of approximately 200 shapes. However, indexing into a significantly larger database is faced with both the lack of a suitable database, and more significantly with the expense related to computing the metric. We have thus (i) gathered shapes from a variety of sources to create a database of over 1000 shapes from forty categories as a stage towards developing an approach for indexing into a much larger database; (ii) developed a coarse-scale approximate similarly measure which relies on the shock graph topology and a very coarse sampling of link attributes. We show that this is a good first-order approximation of the similarly metric and is two orders of magnitude more efficient to compute. An interesting outcome of using this efficient but approximate similarity measure is that the approximation naturally demands a notion of categories to give high precision; (iii) developed an exemplar-based indexing scheme which discards a large number of non-matching shapes solely based on distance to exemplars, coarse scale representatives of each category. The use of a coarse-scale matching measure in conjunction with a coarse-scale sampling of the database leads to a significant reduction in the computational effort without discarding correct matches, thus paving the way for indexing into databases of tens of thousands of shapes.