Case-based reasoning involves reasoning from {\em cases}: specific pieces of experience, the reasoner's or another's, that can be used to solve problems. As a result, case representation is critical: an incomplete case representation limits the system's reasoning power. In this paper we argue for {\em structure-based} case representations, which express arbitrary relations among objects in a flexible way, over more limited or inflexible methods. We motivate the distinction between these kinds of representations with examples from information retrieval systems, CBR systems, and computational models of human analogical reasoning. Structure-based representations provide the benefits of greater expressivity and economy. We give examples of these benefits from two case-based planning systems we have developed, CaPER and CHIRON, and show how the case matching and case acquisition costs can be reduced through the use of massively parallel techniques. (Also cross-referenced as UMIACS-TR-95-56)